ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202132 | #3522. A | Anonyme | 100 | 674ms | 11756kb | C++11 | 1.0kb | 2024-02-13 09:35:03 | 2024-02-13 13:01:42 |
answer
#include <bits/stdc++.h>
using namespace std;
#define QwQ330AwA return 0
#define ll long long
int n;
vector <int> stk[100005];
int tag[100005];
int to[100005];
int ans[100005];
int dfs(int u) {
if (!tag[u]) return ans[u] = u;
if (ans[u]) return ans[u];
return ans[u] = dfs(to[u]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1, siz; i <= n; i++) {
cin >> siz;
for (int j = 1, x; j <= siz; j++) cin >> x, stk[i].push_back(x);
reverse(stk[i].begin(), stk[i].end());
}
for (int i = 1; i <= n; i++) {
if (tag[i]) continue;
if (stk[i].empty()) continue;
int u = i;
while (!tag[u] && !stk[u].empty()) {
tag[u] = i;
to[u] = stk[u].back();
stk[u].pop_back();
u = to[u];
if (tag[u] == i) {//消环
int uu = u;
while (tag[uu] == i) tag[uu] = 0, uu = to[uu];
}
}
}
// for (int i = 1; i <= n; i++) cout << to[i] << ' ' << tag[i] << endl;
for (int i = 1; i <= n; i++) cout << dfs(i) << ' ';
QwQ330AwA;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3628kb
input:
5 61 5 3 5 2 2 3 3 5 3 5 5 2 2 4 3 2 4 3 5 2 5 3 5 1 3 5 5 1 3 3 5 3 2 2 1 5 5 4 5 3 3 3 3 1 4 2 4 1...
output:
3 3 3 3 3
result:
ok single line: '3 3 3 3 3 '
Test #2:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
39 21 21 24 7 35 3 20 7 16 31 16 35 31 13 24 24 22 7 23 23 25 38 20 18 32 25 36 13 15 3 13 31 24 9 3...
output:
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
result:
ok single line: '7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ... 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 '
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
36 25 28 17 24 19 32 22 9 35 9 29 12 4 8 12 6 14 22 15 15 18 33 33 35 10 21 11 15 1 24 13 7 33 25 6 ...
output:
32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 3...
result:
ok single line: '32 32 32 32 32 32 32 32 32 32 ... 32 32 32 32 32 32 32 32 32 36 '
Test #4:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
291 3 80 171 4 0 2 138 25 3 144 186 215 2 23 117 1 61 2 211 33 3 235 267 265 3 112 7 95 1 151 2 70 1...
output:
168 2 34 67 231 25 25 203 34 25 13 170 13 14 232 62 17 168 206 231 231 22 231 24 25 245 245 34 231 2...
result:
ok single line: '168 2 34 67 231 25 25 203 34 2...68 231 129 168 143 143 130 143 '
Subtask #2:
score: 20
Accepted
Test #5:
score: 20
Accepted
time: 43ms
memory: 7624kb
input:
5 155991 2 1 1 5 3 2 2 2 3 4 1 3 5 4 3 4 3 1 1 4 2 2 1 3 5 1 5 1 3 5 1 3 2 5 4 1 2 1 2 5 2 4 4 3 1 5...
output:
3 3 3 3 3
result:
ok single line: '3 3 3 3 3 '
Test #6:
score: 0
Accepted
time: 50ms
memory: 7880kb
input:
38 9068 18 35 4 31 25 9 26 26 6 13 32 14 33 29 15 6 22 13 20 22 4 18 10 8 35 5 22 13 32 7 14 21 37 3...
output:
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 2...
result:
ok single line: '25 25 25 25 25 25 25 25 25 25 ... 25 25 25 25 25 25 25 25 25 25 '
Test #7:
score: 0
Accepted
time: 61ms
memory: 8308kb
input:
290 509 200 281 158 89 96 107 5 119 78 25 142 236 274 179 7 169 147 64 128 161 35 79 239 239 92 249 ...
output:
172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 172 ...
result:
ok single line: '172 172 172 172 172 172 172 17...72 172 172 172 172 172 172 172 '
Test #8:
score: 0
Accepted
time: 57ms
memory: 8980kb
input:
916 4 539 47 501 713 1059 363 649 268 514 409 394 790 851 500 733 306 129 823 471 522 92 164 256 181...
output:
561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 561 ...
result:
ok single line: '561 561 561 561 561 561 561 56...61 561 561 561 561 561 561 561 '
Subtask #3:
score: 30
Accepted
Test #9:
score: 30
Accepted
time: 9ms
memory: 4200kb
input:
937 100 214 276 643 810 401 62 885 509 87 620 307 119 303 54 277 863 811 927 168 422 565 354 95 179 ...
output:
540 634 540 540 540 540 540 540 540 540 540 416 540 540 540 634 540 540 540 540 540 540 540 540 634 ...
result:
ok single line: '540 634 540 540 540 540 540 54...40 540 540 540 540 540 540 540 '
Test #10:
score: 0
Accepted
time: 7ms
memory: 4256kb
input:
2839 8 1148 2834 1775 818 1602 1822 1302 1556 29 2246 1903 152 285 1068 2527 1574 1441 2427 2489 273...
output:
319 319 1300 1944 319 1246 1944 1944 1978 1944 1944 1944 1944 1944 1300 1944 1944 1944 19 319 1944 1...
result:
ok single line: '319 319 1300 1944 319 1246 194...8 2443 1944 1978 1944 1944 827 '
Test #11:
score: 0
Accepted
time: 6ms
memory: 4440kb
input:
9079 0 9 230 2676 5090 3050 6153 2544 5213 8935 2337 5 180 2856 1382 3727 5808 5 7852 2559 6074 1744...
output:
1 2211 2872 6643 4213 2997 2872 6957 6376 10 6113 2080 116 5482 5482 2080 112 887 19 6957 2872 3345 ...
result:
ok single line: '1 2211 2872 6643 4213 2997 287... 6084 1575 5564 1575 6957 6262 '
Test #12:
score: 0
Accepted
time: 16ms
memory: 4920kb
input:
28175 3 24543 16080 20126 1 22773 3 9382 22323 27868 3 8701 26423 26237 2 23599 19638 1 8455 3 22393...
output:
2807 1656 9382 25943 25943 3947 2952 9746 2932 13159 11308 9006 21243 5379 771 19214 17 18 19 10172 ...
result:
ok single line: '2807 1656 9382 25943 25943 394...53 18607 16322 1970 7712 10918 '
Subtask #4:
score: 40
Accepted
Test #13:
score: 40
Accepted
time: 78ms
memory: 9460kb
input:
9054 73 1866 7694 594 3127 7283 7892 7581 8291 3715 5025 2703 2542 6798 8756 8815 3157 4001 3703 416...
output:
8920 118 8920 118 118 118 118 8920 118 281 8920 8920 118 118 118 118 118 118 118 118 118 8920 2611 1...
result:
ok single line: '8920 118 8920 118 118 118 118 ...118 8920 665 118 8920 118 8920 '
Test #14:
score: 0
Accepted
time: 105ms
memory: 10052kb
input:
28899 2 16408 16695 19 15132 13539 4745 19306 530 9631 1500 10923 20152 11845 22548 23589 9876 16802...
output:
1626 9489 2684 702 25529 1102 1626 1626 9 1626 5699 10367 1626 702 11722 1626 17039 702 19 21793 415...
result:
ok single line: '1626 9489 2684 702 25529 1102 ...154 10367 12837 4439 4154 6858 '
Test #15:
score: 0
Accepted
time: 124ms
memory: 11756kb
input:
98666 4 10953 25712 78156 28013 4 24395 62333 24422 91813 7 77654 70681 98040 33482 41662 53920 5756...
output:
3966 24395 35191 20448 58621 58464 7368 28306 58252 45483 36700 16128 6578 25181 15419 549 34592 523...
result:
ok single line: '3966 24395 35191 20448 58621 5...52 55284 6485 6161 16013 46942 '
Test #16:
score: 0
Accepted
time: 114ms
memory: 11540kb
input:
90188 5 743 36408 87777 62975 75146 1 86274 8 61634 86090 72839 20401 40232 65247 80289 57993 10 193...
output:
39455 20806 5351 19908 7396 59205 43326 57942 47670 42726 62557 48994 78690 34708 56392 6382 67095 6...
result:
ok single line: '39455 20806 5351 19908 7396 59... 54805 55268 85082 40926 36661 '
Extra Test:
score: 0
Extra Test Passed