UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202132#3522. AAnonyme100674ms11756kbC++111.0kb2024-02-13 09:35:032024-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;
}

Details

小提示:点击横条可展开更详细的信息

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