QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#93775#6149. 占领世界Renshey100 ✓1357ms142644kbC++233.2kb2023-04-02 10:38:202023-04-02 10:38:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-02 10:38:22]
  • 评测
  • 测评结果:100
  • 用时:1357ms
  • 内存:142644kb
  • [2023-04-02 10:38:20]
  • 提交

answer

#include <bits/stdc++.h>
const int maxn = 500000 + 10;
int n, S, T;
std::vector<int> e[maxn];
struct Subtask1
{
	int ans, f[maxn], g[maxn], pos[maxn];
	std::vector<std::pair<int, int>> F[maxn];
	std::vector<int> pre[maxn], suf[maxn];
	inline void dfs1(int u, int fr)
	{
		for (int v : e[u])
			if (v != fr)
				dfs1(v, u), F[u].push_back(std::make_pair(f[v], v));
		std::sort(F[u].begin(), F[u].end(), std::greater<std::pair<int, int>>());
		for (int i = 0; i < (int)F[u].size(); i++)
			f[u] = std::max(f[u], F[u][i].first + i + 1);
	}
	inline void dfs2(int u, int fr)
	{
		if (fr)
			F[u].push_back(std::make_pair(g[fr], fr));
		std::sort(F[u].begin(), F[u].end(), std::greater<std::pair<int, int>>());
		for (int i = 0; i < (int)F[u].size(); i++)
			if (F[u][i].second != fr)
				pos[F[u][i].second] = i;
		int m = (int)F[u].size();
		pre[u].resize(m);
		suf[u].resize(m);
		for (int i = 0; i < m; i++)
			pre[u][i] = suf[u][i] = F[u][i].first + i + 1;
		for (int i = 1; i < m; i++)
			pre[u][i] = std::max(pre[u][i], pre[u][i - 1]);
		for (int i = m - 2; ~i; i--)
			suf[u][i] = std::max(suf[u][i], suf[u][i + 1]);
		ans = std::min(ans, suf[u][0]);
		for (int v : e[u])
			if (v != fr)
			{
				g[u] = 0;
				if (pos[v] > 0)
					g[u] = std::max(g[u], pre[u][pos[v] - 1]);
				if (pos[v] < m - 1)
					g[u] = std::max(g[u], suf[u][pos[v] + 1] - 1);
				dfs2(v, u);
			}
	}
	inline void solve(void)
	{
		dfs1(1, 0);
		ans = f[1];
		dfs2(1, 0);
		printf("%d\n", ans);
	}
} S1;
struct Subtask2
{
	int a[maxn], m, f[maxn], pre[maxn], fa[maxn];
	std::vector<int> F[maxn];
	bool tag[maxn];
	inline void dfs(int u, int fr)
	{
		fa[u] = fr;
		for (int v : e[u])
			if (v != fr)
				dfs(v, u);
	}
	inline int dfs_pre(int u, int fr)
	{
		std::vector<int> F;
		int res = 0;
		for (int v : e[u])
			if (v != fr)
				F.push_back(dfs_pre(v, u));
		std::sort(F.begin(), F.end(), std::greater<int>());
		for (int i = 0; i < (int)F.size(); i++)
			res = std::max(res, F[i] + i + 1);
		return res;
	}
	inline bool check(int x)
	{
		int lpos = 1, rpos = m;
		for (int t = x; lpos <= m; t--, lpos++)
		{
			if (t < f[lpos])
			{
				lpos--;
				break;
			}
			if (t == f[lpos])
				t -= pre[lpos];
		}
		for (int t = x; rpos >= 1; t--, rpos--)
		{
			if (t < f[rpos])
			{
				rpos++;
				break;
			}
			if (t == f[rpos])
				t -= pre[rpos];
		}
		return rpos - lpos <= 1;
	}
	inline void solve(void)
	{
		dfs(T, 0);
		for (int u = S; u; u = fa[u])
			a[++m] = u, tag[u] = true;
		for (int i = 1; i <= m; i++)
		{
			int u = a[i];
			for (int v : e[u])
				if (!tag[v])
					F[i].push_back(dfs_pre(v, u));
			std::sort(F[i].begin(), F[i].end(), std::greater<int>());
			for (int j = 0; j < (int)F[i].size(); j++)
				if (F[i][j] + j + 1 >= f[i])
					f[i] = F[i][j] + j + 1, pre[i] = j + 1;
		}
		int l = 0, r = n;
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (check(mid))
				r = mid;
			else
				l = mid + 1;
		}
		printf("%d\n", l);
	}
} S2;
signed main()
{
	scanf("%d%d%d", &n, &S, &T);
	for (int i = 1, u, v; i < n; i++)
		scanf("%d%d", &u, &v), e[u].push_back(v), e[v].push_back(u);
	S1.solve();
	S2.solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 23ms
memory: 67168kb

input:

3000 426 2975
31 1763
115 539
961 847
501 833
1545 1944
2660 2997
2127 2235
2236 1797
464 2773
2527 1365
967 1525
2290 1087
2785 1705
1790 1049
354 2216
1375 736
1330 1489
1274 2291
2335 1775
475 1232
1070 486
1580 196
72 815
2344 535
940 1871
1900 1906
747 1189
2992 531
245 1782
1931 598
1349 306
1...

output:

53
90

result:

ok 2 lines

Test #2:

score: 10
Accepted
time: 13ms
memory: 65360kb

input:

3000 670 115
1835 2667
2147 230
71 763
464 2598
2594 1719
800 1397
2132 2706
1981 198
583 1660
1039 2045
65 2503
223 1867
154 1154
1247 598
695 2268
1065 2881
1934 563
110 2357
1326 573
1954 1271
2643 2753
2667 1774
2458 1648
1971 393
307 9
2437 724
2863 2659
2942 369
812 1541
1318 1858
808 2382
173...

output:

53
73

result:

ok 2 lines

Test #3:

score: 10
Accepted
time: 647ms
memory: 111828kb

input:

300000 92087 262371
7926 272168
152466 71969
52235 185998
82087 210656
143836 256180
256385 227879
18141 36161
201697 3913
26204 16472
247759 58673
192685 149329
117555 52754
99235 242319
254389 279583
168990 285133
48558 235584
237179 65265
209906 254607
185996 235584
247145 216818
154452 52754
186...

output:

1052
1056

result:

ok 2 lines

Test #4:

score: 10
Accepted
time: 731ms
memory: 112256kb

input:

300000 92087 262371
7926 272168
152466 71969
52235 185998
82087 210656
143836 256180
256385 227879
18141 36161
201697 3913
26204 16472
247759 58673
192685 149329
117555 52754
99235 242319
254389 279583
168990 285133
48558 235584
237179 65265
209906 254607
185996 235584
247145 216818
154452 52754
186...

output:

1052
1056

result:

ok 2 lines

Test #5:

score: 10
Accepted
time: 1226ms
memory: 136724kb

input:

500000 308457 387900
470725 19330
235921 380991
322121 130699
190619 208567
303156 332243
473855 44543
142622 225334
214444 168055
432839 424754
327565 413405
427933 376457
213359 162384
208648 357831
216335 357491
374988 41143
261742 362064
76824 497662
243054 415296
128360 450024
123862 431516
282...

output:

305
433

result:

ok 2 lines

Test #6:

score: 10
Accepted
time: 1333ms
memory: 135884kb

input:

500000 308457 387900
470725 19330
235921 380991
322121 130699
190619 208567
303156 332243
473855 44543
142622 225334
214444 168055
432839 424754
327565 413405
427933 376457
213359 162384
208648 357831
216335 357491
374988 41143
261742 362064
76824 497662
243054 415296
128360 450024
123862 431516
282...

output:

305
433

result:

ok 2 lines

Test #7:

score: 10
Accepted
time: 1217ms
memory: 135856kb

input:

500000 13719 420885
399317 381277
41676 275757
138975 281666
191698 170770
311003 224617
173223 407810
227575 207996
276157 123646
432387 55947
410986 176870
451327 121347
273575 419400
384793 75848
68371 100471
324344 98441
21356 223660
479717 79383
499416 118692
377401 207466
289461 188403
432082 ...

output:

319
329

result:

ok 2 lines

Test #8:

score: 10
Accepted
time: 1259ms
memory: 136580kb

input:

500000 237652 50999
266232 210311
376044 459160
125750 258890
426135 147596
329246 407974
310617 332803
235756 79274
137332 486272
480522 286743
167736 171616
147892 432458
92532 345730
289021 338565
172999 197281
191951 427002
248280 458182
153664 140675
417342 279414
399565 359828
443361 228810
28...

output:

565
728

result:

ok 2 lines

Test #9:

score: 10
Accepted
time: 1264ms
memory: 136304kb

input:

500000 62609 260214
150684 264206
147601 195366
428225 289295
92208 108123
454516 301327
329666 31011
83690 124299
146803 240123
110098 154811
339177 460841
113758 313839
305160 236235
456816 269750
84211 490154
56323 163171
266720 207006
443728 430672
402371 371952
219966 10930
480075 190834
312256...

output:

299
382

result:

ok 2 lines

Test #10:

score: 10
Accepted
time: 1357ms
memory: 142644kb

input:

500000 238685 17245
277255 57523
65604 234360
432163 161542
337766 168779
96465 168779
243469 60686
494476 256521
151114 90629
273743 144403
320142 255422
435812 170174
86896 378559
303445 381442
47005 317198
347817 361225
30743 99739
355838 400233
322384 188685
219234 290255
188567 289628
155626 37...

output:

1056
1054

result:

ok 2 lines