QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#93775 | #6149. 占领世界 | Renshey | 100 ✓ | 1357ms | 142644kb | C++23 | 3.2kb | 2023-04-02 10:38:20 | 2023-04-02 10:38:22 |
Judging History
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