API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 17th, 2015
430
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.93 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. #include<algorithm>
  5. #include<cstdio>
  6. #include<numeric>
  7. #include<cstring>
  8. #include<ctime>
  9. #include<cstdlib>
  10. #include<set>
  11. #include<map>
  12. #include<unordered_map>
  13. #include<unordered_set>
  14. #include<list>
  15. #include<cmath>
  16. #include<bitset>
  17. #include<cassert>
  18. using namespace std;
  19. typedef vector<int> vi;
  20.  
  21. const int N = 1009;
  22. const int inf = (int) 2e9;
  23. const int MAXN = 1000, LOGMAXN = 20;
  24. const int INF = 1000 * 1000 * 1000 + 7;
  25. #define PB push_back
  26. #define SZ(s) (int) s.size ()
  27. struct test
  28. {
  29. int n, m;
  30. vector<pair<int, int> >edges;
  31. vector<pair<int, int> >queries;
  32. };
  33. struct stupid
  34. {
  35.  
  36. int n;
  37. int m;
  38.  
  39. int l;
  40. int cnt;
  41. int timer;
  42. int tin[N];
  43. int tout[N];
  44. int dist[N];
  45. int up[N][50];
  46.  
  47. int u[N];
  48. int sz[N];
  49. int par[N];
  50. int ans[N];
  51.  
  52. vi g[N];
  53. vi d[N];
  54. stupid()
  55. {
  56. n = 0;
  57. m = 0;
  58. l = 0;
  59. cnt = 0;
  60. timer = 0;
  61. for (int i = 0; i < N; i++)
  62. {
  63. tin[i] = 0;
  64. tout[i] = 0;
  65. dist[i] = 0;
  66. for (int j = 0; j < 50; j++)
  67. {
  68. up[i][j] = 0;
  69. }
  70. u[i] = 0;
  71. sz[i] = 0;
  72. par[i] = 0;
  73. ans[i] = 0;
  74. g[i] = vector<int>();
  75. d[i] = vector<int>();
  76. }
  77. }
  78. void dfs0(int v, int p = 0) {
  79. tin[v] = timer++;
  80. up[v][0] = p;
  81. for (int i = 1; i <= l; i++) {
  82. up[v][i] = up[up[v][i - 1]][i - 1];
  83. }
  84. for (int i = 0; i < SZ(g[v]); i++) {
  85. int to = g[v][i];
  86. if (to != p) {
  87. dist[to] = dist[v] + 1;
  88. dfs0(to, v);
  89. }
  90. }
  91. tout[v] = timer++;
  92. }
  93. void dfs1(int v, int p = -1) {
  94. cnt++;
  95. sz[v] = 1;
  96. for (int i = 0; i < SZ(g[v]); i++) {
  97. int to = g[v][i];
  98. if (to == p || u[to]) {
  99. continue;
  100. }
  101. else {
  102. dfs1(to, v);
  103. sz[v] += sz[to];
  104. }
  105. }
  106. }
  107. int dfs2(int v, int p = -1) {
  108. int mx = cnt - sz[v];
  109. for (int i = 0; i < SZ(g[v]); i++) {
  110. int to = g[v][i];
  111. if (!u[to] && to != p) {
  112. mx = max(mx, sz[to]);
  113. }
  114. }
  115. if (mx <= cnt / 2) {
  116. return v;
  117. }
  118. else {
  119. for (int i = 0; i < SZ(g[v]); i++) {
  120. int to = g[v][i];
  121. if (to == p || u[to]) {
  122. continue;
  123. }
  124. else {
  125. int res = dfs2(to, v);
  126. if (res != -1) {
  127. return res;
  128. }
  129. }
  130. }
  131. }
  132. return -1;
  133. }
  134. void dfs3(int v) {
  135. for (int i = 0; i < SZ(d[v]); i++) {
  136. int to = d[v][i];
  137. if (to != par[v]) {
  138. par[to] = v;
  139. dfs3(to);
  140. }
  141. }
  142. }
  143. int decompose(int v) {
  144. cnt = 0;
  145. dfs1(v);
  146. int c = dfs2(v);
  147. u[c] = 1;
  148. for (int i = 0; i < SZ(g[c]); i++) {
  149. int to = g[c][i];
  150. if (!u[to]) {
  151. to = decompose(to);
  152. d[c].PB(to);
  153. d[to].PB(c);
  154. }
  155. }
  156. return c;
  157. }
  158. bool upper(int a, int b) {
  159. return tin[a] <= tin[b] && tout[b] <= tout[a];
  160. }
  161. int lca(int a, int b) {
  162. if (upper(a, b)) {
  163. return a;
  164. }
  165. else if (upper(b, a)) {
  166. return b;
  167. }
  168. else {
  169. for (int i = l; i >= 0; i--) {
  170. if (!upper(up[a][i], b)) {
  171. a = up[a][i];
  172. }
  173. }
  174. return up[a][0];
  175. }
  176. }
  177. int f(int a, int b) {
  178. return dist[a] + dist[b] - 2 * dist[lca(a, b)];
  179. }
  180. void update(int v) {
  181. int u = v;
  182. while (v != -1) {
  183. ans[v] = min(ans[v], f(u, v));
  184. v = par[v];
  185. }
  186. }
  187. int get(int v) {
  188. int u = v;
  189. int res = inf;
  190. while (v != -1) {
  191. res = min(res, ans[v] + f(u, v));
  192. v = par[v];
  193. }
  194. return res;
  195. }
  196. vector<int>solve(test t)
  197. {
  198. n = t.n;
  199. m = t.m;
  200. for (int i = 0; i < n - 1; i++) {
  201. int a, b;
  202. a = t.edges[i].first;
  203. b = t.edges[i].second;
  204. g[a].PB(b);
  205. g[b].PB(a);
  206. }
  207. while ((1 << l) <= n) {
  208. l++;
  209. }
  210. dfs0(1);
  211. int c = decompose(1);
  212. for (int i = 1; i <= n; i++) {
  213. par[i] = -1;
  214. ans[i] = inf;
  215. }
  216. dfs3(c);
  217. for (int i = 1; i <= n; i++) {
  218. if (i != c) {
  219. assert(par[i] != -1);
  220. }
  221. }
  222. update(1);
  223. vector<int>res;
  224. for (int i = 0; i < m; i++)
  225. {
  226. int x, v;
  227. x = t.queries[i].first;
  228. v = t.queries[i].second;
  229. if (x == 1) {
  230. update(v);
  231. }
  232. else {
  233. res.push_back(get(v));
  234. }
  235. }
  236. return res;
  237. }
  238. };
  239.  
  240. struct smart
  241. {
  242. vector<int>tree[MAXN];
  243. int height[MAXN], timeIn[MAXN], timeOut[MAXN];
  244. int ancestor[MAXN][LOGMAXN];
  245. bool used[MAXN];
  246. bool used2[MAXN];
  247. bool wasCentroid[MAXN];
  248. int subtreeSize[MAXN];
  249. int decompositionParent[MAXN];
  250. int bestLen[MAXN], bestPos[MAXN];
  251. int dfsTimer = 1;
  252. smart()
  253. {
  254. for (int i = 0; i < MAXN; i++)
  255. {
  256. tree[i] = vector<int>();
  257. height[i] = 0;
  258. timeIn[i] = 0;
  259. timeOut[i] = 0;
  260. for (int j = 0; j < LOGMAXN; j++)
  261. {
  262. ancestor[i][j] = 0;
  263. }
  264. used[i] = false;
  265. used2[i] = false;
  266. wasCentroid[i] = false;
  267. subtreeSize[i] = 0;
  268. decompositionParent[i] = 0;
  269. bestLen[i] = 0;
  270. bestPos[i] = 0;
  271.  
  272. }
  273. }
  274. void clearFull(int n)
  275. {
  276. for (int i = 1; i <= n; i++)
  277. {
  278. used[i] = false;
  279. used2[i] = false;
  280. subtreeSize[i] = 0;
  281. }
  282. }
  283. void precalcLCA(int v, int parent = 1, int curHeight = 1)
  284. {
  285. used[v] = true;
  286. timeIn[v] = dfsTimer;
  287. dfsTimer++;
  288. ancestor[v][0] = parent;
  289. height[v] = curHeight;
  290. for (int i = 1; i < LOGMAXN; i++)
  291. {
  292. ancestor[v][i] = ancestor[ancestor[v][i - 1]][i - 1];
  293. }
  294. for (int i = 0; i < tree[v].size(); i++)
  295. {
  296. int to = tree[v][i];
  297. if (!used[to])
  298. {
  299. precalcLCA(to, v, curHeight + 1);
  300. }
  301. }
  302. timeOut[v] = dfsTimer;
  303. dfsTimer++;
  304. }
  305. bool isAncestor(int u, int v)
  306. {
  307. return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
  308. }
  309. int LCA(int u, int v)
  310. {
  311. for (int i = LOGMAXN - 1; i >= 0; i--)
  312. {
  313. if (!isAncestor(ancestor[u][i], v))
  314. {
  315. u = ancestor[u][i];
  316. }
  317. }
  318. return ancestor[u][0];
  319. }
  320. int verticalPathLength(int u, int v)
  321. {
  322. return height[v] - height[u];
  323. }
  324. int pathLength(int u, int v)
  325. {
  326. if (isAncestor(u, v))
  327. {
  328. return verticalPathLength(u, v);
  329. }
  330. else if (isAncestor(v, u))
  331. {
  332. return verticalPathLength(v, u);
  333. }
  334. else
  335. {
  336. int lca = LCA(u, v);
  337. return verticalPathLength(lca, u) + verticalPathLength(lca, v);
  338. }
  339. }
  340. void calcSizes(int v)
  341. {
  342. used[v] = true;
  343. subtreeSize[v] = 1;
  344. for (int i = 0; i < tree[v].size(); i++)
  345. {
  346. int to = tree[v][i];
  347. if (!used[to] && !wasCentroid[to])
  348. {
  349. calcSizes(to);
  350. subtreeSize[v] += subtreeSize[to];
  351. }
  352. }
  353. }
  354. int findCentroid(int v, int rootSize = -1, int upSize = 0)
  355. {
  356. used2[v] = true;
  357. if (rootSize == -1)
  358. {
  359. rootSize = (subtreeSize[v] + 1) / 2;
  360. }
  361. int ans = -1;
  362. bool isCentroid = true;
  363. if (upSize > rootSize) isCentroid = false;
  364. for (int i = 0; i < tree[v].size(); i++)
  365. {
  366. int to = tree[v][i];
  367. if (!used2[to] && !wasCentroid[to] && subtreeSize[to] > rootSize) isCentroid = false;
  368. }
  369. if (isCentroid)
  370. {
  371. ans = v;
  372. }
  373. for (int i = 0; i < tree[v].size(); i++)
  374. {
  375. int to = tree[v][i];
  376. if (!used2[to] && !wasCentroid[to])
  377. {
  378. int tmp = findCentroid(to, rootSize, upSize + subtreeSize[v] - subtreeSize[to]);
  379. if (tmp != -1)
  380. {
  381. ans = tmp;
  382. }
  383. }
  384. }
  385. return ans;
  386. }
  387. void color(int v)
  388. {
  389. int u = v;
  390. while (u != -1)
  391. {
  392. int curLen = pathLength(u, v);
  393. if (curLen < bestLen[u])
  394. {
  395. bestLen[u] = curLen;
  396. bestPos[u] = v;
  397. }
  398. u = decompositionParent[u];
  399. }
  400. }
  401. int findNearest(int v)
  402. {
  403. int u = v;
  404. int ans = INF;
  405. while (u != -1)
  406. {
  407. if (bestPos[u] != -1)
  408. {
  409. ans = min(ans, pathLength(bestPos[u], v));
  410. }
  411. u = decompositionParent[u];
  412. }
  413. return ans;
  414. }
  415. vector<int>solve(test t)
  416. {
  417. // freopen("input.txt", "r", stdin);
  418. // freopen("output.txt", "w", stdout);
  419. int n, m;
  420. n = t.n;
  421. m = t.m;
  422. for (int i = 0; i < n - 1; i++)
  423. {
  424. int u, v;
  425. //scanf("%d%d", &u, &v);
  426. //u = i;
  427. //v = i + 1;
  428. u = t.edges[i].first;
  429. v = t.edges[i].second;
  430. tree[u].push_back(v);
  431. tree[v].push_back(u);
  432. }
  433. precalcLCA(1);
  434. clearFull(n);
  435. calcSizes(1);
  436. int decompositionRoot = findCentroid(1);
  437. decompositionParent[decompositionRoot] = -1;
  438. wasCentroid[decompositionRoot] = true;
  439. vector<int>lastLayer;
  440. lastLayer.push_back(decompositionRoot);
  441. int lcnt = 0;
  442. while (!lastLayer.empty())
  443. {
  444. lcnt++;
  445. assert(lcnt < 40);
  446. clearFull(n);
  447. vector<int>newCentroids;
  448. for (int i = 0; i < lastLayer.size(); i++)
  449. {
  450. int v = lastLayer[i];
  451. for (int j = 0; j < tree[v].size(); j++)
  452. {
  453. int to = tree[v][j];
  454. if (!wasCentroid[to] && !used[to])
  455. {
  456. calcSizes(to);
  457. int curCenter = findCentroid(to);
  458. decompositionParent[curCenter] = v;
  459. wasCentroid[curCenter] = true;
  460. newCentroids.push_back(curCenter);
  461. }
  462. }
  463. }
  464. lastLayer = newCentroids;
  465. }
  466. for (int i = 1; i <= n; i++)
  467. {
  468. bestLen[i] = INF;
  469. bestPos[i] = -1;
  470. }
  471. color(1);
  472. vector<int>res;
  473. for (int i = 0; i < m; i++)
  474. {
  475. int type;
  476. //scanf("%d", &type);
  477. type = t.queries[i].first;
  478. if (type == 1)
  479. {
  480. int v;
  481. v = t.queries[i].second;
  482. color(v);
  483. }
  484. else
  485. {
  486. int v;
  487. v = t.queries[i].second;
  488. res.push_back(findNearest(v));
  489. }
  490. }
  491. return res;
  492. }
  493. };
  494. test gen(int n, int m)
  495. {
  496. test ans;
  497. ans.n = n;
  498. ans.m = m;
  499. for (int i = 2; i <= n; i++)
  500. {
  501. ans.edges.push_back(make_pair(rand() % (i - 1) + 1, i));
  502. }
  503. for (int i = 0; i < m; i++)
  504. {
  505. ans.queries.push_back(make_pair(rand() % 2 + 1, rand() % n + 1));
  506. }
  507. return ans;
  508. }
  509. int main()
  510. {
  511. int cnt = 0;
  512. freopen("output.txt", "w", stdout);
  513. while (1)
  514. {
  515. test t = gen(10, 10);
  516. stupid st = stupid();
  517. smart sm = smart();
  518. vector<int>ans1 = st.solve(t);
  519. vector<int>ans2 = sm.solve(t);
  520. bool ok = true;
  521. if (ans1.size() != ans2.size())
  522. {
  523. ok = false;
  524. }
  525. for (int i = 0; i < ans1.size(); i++)
  526. {
  527. if (ans1[i] != ans2[i])
  528. {
  529. ok = false;
  530. }
  531. }
  532. if (!ok)
  533. {
  534. printf("%d %d\n", t.n, t.m);
  535. for (int i = 0; i < t.n - 1; i++)
  536. {
  537. printf("%d %d\n", t.edges[i].first, t.edges[i].second);
  538. }
  539. for (int i = 0; i < t.m; i++)
  540. {
  541. printf("%d %d\n", t.queries[i].first, t.queries[i].second);
  542. }
  543. return 0;
  544. }
  545. cnt++;
  546. cerr << cnt << " Tests passed" << endl;
  547. }
  548. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!