QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#233673 | #3026. Little Worm | jerzyk# | AC ✓ | 360ms | 15068kb | C++20 | 4.3kb | 2023-10-31 21:16:15 | 2023-10-31 21:16:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
const int N = 100 * 1000 + 7;
bool od[N];
vector<int> ed[N], pth, cura;
int wys[N], mwy[N], wh[N], oj[N];
bool DFSP(int v, int tar)
{
od[v] = true;
if(v == tar)
{pth.pb(v); return true;}
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(od[ed[v][i]]) continue;
if(DFSP(ed[v][i], tar))
{
pth.pb(v);
return true;
}
}
return false;
}
void DFS(int v)
{
mwy[v] = wys[v]; wh[v] = v;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
if(wys[ed[v][i]]) continue;
wys[ed[v][i]] = wys[v] + 1; oj[ed[v][i]] = v;
DFS(ed[v][i]);
if(mwy[ed[v][i]] > mwy[v])
{
mwy[v] = mwy[ed[v][i]];
wh[v] = ed[v][i];
}
}
}
inline void Pth(int a, int b, int n)
{
pth.clear();
DFSP(b, a);
for(int i = 1; i <= n; ++i) od[i] = false;
}
void DoA(int a, int b, int tar, int d, int n)
{
cura.clear();
wys[tar] = 1; DFS(tar);
while(cura.size() <= 10 * n)
{
int pa = a, pb = b;
if(b == tar || a == tar) break;
int il = mwy[a] - wys[a] + 1, cur = b, g = 0;
for(int i = 1; i <= il; ++i)
{
if(mwy[cur] > mwy[g]) g = cur;
cur = oj[cur];
}
if(mwy[a] >= d) g = tar;
while(b != g)
{
cura.pb(wh[a]);
a = wh[a]; b = oj[b];
}
if(b == tar || a == tar) break;
il = mwy[b] - wys[b] + 1, cur = a, g = 0;
for(int i = 1; i <= il; ++i)
{
if(mwy[cur] > mwy[g]) g = cur;
cur = oj[cur];
}
if(mwy[b] >= d) g = tar;
while(a != g)
{
cura.pb(wh[b]);
b = wh[b]; a = oj[a];
}
if(b == tar || a == tar) break;
if(pa == a && pb == b)
{
cura.pb(-1);
return;
}
}
for(int i = 1; i <= n; ++i)
{
wys[i] = 0; oj[i] = 0;
}
}
int DoR(int a, int b, int tar, int d, int n)
{
for(int i = 1; i <= n; ++i)
{
wys[i] = 0; oj[i] = 0;
}
cura.clear();
wys[tar] = 1; DFS(tar);
while(cura.size() <= 10 * n)
{
//cout << "p " << a << " " << b << "\n";
int pa = a, pb = b;
if(b == tar || a == tar) break;
int il = mwy[a] - wys[a] + 1, cur = b, g = b;
for(int i = 1; i <= il; ++i)
{
if(mwy[cur] > mwy[g]) g = cur;
cur = oj[cur];
}
if(mwy[a] >= d) g = tar;
while(b != g)
{
cura.pb(b);
a = wh[a]; b = oj[b];
}
if(b == tar || a == tar) break;
il = mwy[b] - wys[b] + 1; cur = a; g = a;
for(int i = 1; i <= il; ++i)
{
if(mwy[cur] > mwy[g]) g = cur;
cur = oj[cur];
}
if(mwy[b] >= d) g = tar;
//cout << g << " " << mwy[b] << "\n";
while(a != g)
{
cura.pb(a);
b = wh[b]; a = oj[a];
}
if(b == tar || a == tar) break;
if(pa == a && pb == b) return -1;
}
for(int i = 1; i <= n; ++i)
{
wys[i] = 0; oj[i] = 0;
}
reverse(cura.begin(), cura.end());
if(a == tar) return b;
return a;
}
void Solve()
{
int n, a, b, c, d, x, y, di;
int dok;
vector<int> ans, pab, pcd, pac;
cin >> n;
for(int i = 1; i <= n; ++i)
{
wys[i] = 0; od[i] = false;
ed[i].clear();
}
for(int i = 1; i < n; ++i)
{
cin >> a >> b;
ed[a].pb(b); ed[b].pb(a);
}
cin >> a >> b;
cin >> c >> d;
Pth(a, b, n); pab = pth;
Pth(c, d, n); pcd = pth;
Pth(a, c, n); pac = pth;
for(int i = 0; i < (int)min(pab.size(), pac.size()); ++i)
if(pab[i] == pac[i]) x = pab[i];
reverse(pac.begin(), pac.end());
for(int i = 0; i < (int)min(pcd.size(), pac.size()); ++i)
if(pcd[i] == pac[i]) y = pcd[i];
reverse(pac.begin(), pac.end());
di = pab.size();
DoA(a, b, x, di, n);
ans = cura;
dok = DoR(c, d, y, di, n);
//cout << "\n " << dok << " " << x << " " << y << "\n";
if(cura.size() + ans.size() > 10 * n || dok == -1 || (ans.size() > 0 && ans.back() == -1))
{
cout << -1 << "\n";
return;
}
Pth(x, dok, n);
for(int i = 1; i < (int)pth.size(); ++i) ans.pb(pth[i]);
for(int i = 0; i < (int)cura.size(); ++i) ans.pb(cura[i]);
if(ans.size() > 10 * n)
{
cout << -1 << "\n";
return;
}
cout << ans.size() << "\n";
for(int i = 0; i < (int)ans.size(); ++i)
cout << ans[i] << " ";
cout << "\n";
for(int i = 1; i <= n; ++i)
{
wys[i] = 0; od[i] = false;
ed[i].clear();
}
pth.clear(); cura.clear();
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int _=1;
cin >> _;
while(_--) Solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 156ms
memory: 7424kb
input:
7000 92 50 58 92 77 24 21 57 67 63 78 40 90 57 92 73 45 87 85 68 43 11 46 87 7 70 9 62 25 45 80 76 57 49 86 10 48 10 83 88 82 7 82 5 31 16 42 75 84 33 6 28 2 56 5 81 64 11 33 17 38 35 63 4 31 54 90 86 65 23 91 15 30 66 71 53 37 48 27 69 59 67 32 92 50 71 8 74 52 79 75 25 88 41 55 40 39 60 47 49 12 4...
output:
79 54 7 87 85 89 13 44 19 91 23 61 52 74 26 18 29 68 43 83 10 48 27 55 41 82 88 25 62 8 71 66 70 9 3 77 51 46 11 33 6 79 75 84 42 20 2 28 56 5 31 4 92 50 58 37 53 22 14 16 15 30 78 63 35 57 76 80 45 73 81 36 17 38 67 47 60 64 1 32 79 51 60 48 90 37 10 20 45 46 32 4 75 50 43 68 26 87 55 63 3 86 54 2...
result:
ok OK!
Test #2:
score: 0
Accepted
time: 194ms
memory: 6612kb
input:
470 743 429 611 226 347 611 87 507 72 23 589 673 27 563 260 567 724 316 41 89 470 292 80 11 218 139 32 145 422 394 296 706 552 581 20 358 491 632 40 390 284 224 506 141 491 541 202 533 669 122 273 421 350 566 607 275 205 126 352 195 491 469 445 259 426 624 547 135 339 503 325 639 444 677 53 459 425 ...
output:
-1 9 373 412 781 163 492 383 20 96 846 3571 3587 1715 1536 1705 885 790 319 1148 2981 1218 116 560 2830 3652 2794 1953 736 1502 672 2134 2464 3230 1404 606 2980 3503 3062 2266 2466 3461 2903 2504 362 329 3563 1208 2372 767 1960 2941 294 557 1797 1557 2735 2806 3537 940 520 479 3391 3610 2819 171 29...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 360ms
memory: 15068kb
input:
11 88832 31434 32960 21975 48728 73507 72853 8790 28585 34700 9499 84885 4809 17607 74921 38812 7277 15324 70994 21922 45093 27594 4262 73567 70888 34197 37341 5364 29062 72260 6143 40230 15118 13890 40327 26144 60801 18852 11719 35653 12248 60905 79198 69712 1971 18796 12498 49133 34898 84942 72077...
output:
88411 23337 34664 13391 11058 9943 16165 28102 21488 25850 30444 60 71581 53549 80422 49420 32241 13254 68001 38263 66843 30309 55824 27575 10732 6658 27026 36977 50108 26722 38490 10127 51757 49701 78692 56502 53233 82620 10595 36902 3429 50559 66459 30132 81728 82615 74409 27123 50368 17741 20437 ...
result:
ok OK!