QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791603#9743. 重心树bluejellyfishWA 27ms3848kbC++23708b2024-11-28 19:49:132024-11-28 19:49:13

Judging History

This is the latest submission verdict.

  • [2024-11-28 19:49:13]
  • Judged
  • Verdict: WA
  • Time: 27ms
  • Memory: 3848kb
Show
  • [2024-11-28 19:49:13]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
//#define x first
//#define y second
const int mod = 1e9 + 7;
int f[300000];
int find(int x) {
	if(x != f[x]) x = f[x] = f[f[x]];
	return f[x];
}
void miss() {
	int n;
	cin >> n;
	vector<vector<int>>mp(n + 1);
	for(int i = 1; i <= n; i++) {
		f[i] = i;
		int x;
		for(cin >> x; x; x--) {
			int it;
			cin >> it;
			mp[i].push_back(it);
		}
	}
	for(int i = n; i; i--) {
		for(auto x : mp[i]) {
			cout << i << " " << find(x) << endl;
			f[find(x)] = i;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
    cin >> T;
	while(T--) miss();
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3848kb

input:

2
4
2 3 4
1 3
0
0
3
1 3
1 3
0

output:

2 3
1 2
1 4
2 3
1 2

result:

ok Accepted (2 test cases)

Test #2:

score: 0
Accepted
time: 27ms
memory: 3560kb

input:

40000
3
2 2 3
0
0
2
1 2
0
4
2 4 3
1 4
0
0
5
1 3
2 5 4
1 5
0
0
4
3 2 3 4
0
0
0
2
1 2
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
2
1 2
0
2
1 2
0
5
4 2 3 4 5
0
0
0
0
4
1 2
2 3 4
0
0
5
2 5 4
1 5
1 4
0
0
2
1 2
0
5
1 2
3 3 4 5
0
0
0
5
2 2 3
0
2 4 5
0
0
5
2 5 4
1 5
1 4
0
0
5
2 2 4
2 3 5
0
0
0
4
1 3
1 4
1 4
0
4
2 4 3
1 ...

output:

1 2
1 3
1 2
2 4
1 2
1 3
3 5
2 3
2 4
1 2
1 2
1 3
1 4
1 2
1 2
2 3
2 4
2 5
1 2
1 2
1 2
1 2
1 3
1 4
1 5
2 3
2 4
1 2
3 4
2 5
1 2
1 3
1 2
2 3
2 4
2 5
1 2
3 4
3 5
1 2
1 3
3 4
2 5
1 2
1 3
2 3
2 5
1 2
1 4
3 4
2 3
1 2
2 4
1 2
1 3
2 3
1 2
3 5
2 4
1 2
1 3
1 2
2 3
1 2
3 4
3 5
2 3
1 2
1 2
3 4
2 3
1 2
4 5
2 4
1 2
...

result:

ok Accepted (40000 test cases)

Test #3:

score: 0
Accepted
time: 11ms
memory: 3528kb

input:

10000
5
2 3 4
1 5
1 5
0
0
4
2 3 4
1 3
0
0
7
1 2
3 4 7 6
1 4
0
1 7
0
0
2
1 2
0
2
1 2
0
8
1 3
1 4
3 4 5 6
2 7 8
0
0
0
0
4
2 2 4
0
1 4
0
4
1 2
2 3 4
0
0
4
1 2
2 3 4
0
0
2
1 2
0
7
3 3 4 6
1 7
1 7
0
1 6
0
0
4
2 4 3
1 4
0
0
3
2 2 3
0
0
6
2 5 4
1 6
1 4
0
1 6
0
3
2 2 3
0
0
5
3 2 5 4
0
1 5
0
0
7
2 4 6
1 5
1 ...

output:

3 5
2 3
1 2
1 4
2 3
1 2
1 4
5 7
3 4
2 3
2 5
2 6
1 2
1 2
1 2
4 7
4 8
3 4
3 5
3 6
2 3
1 2
3 4
1 2
1 3
2 3
2 4
1 2
2 3
2 4
1 2
1 2
5 6
3 7
2 3
1 2
1 4
1 5
2 4
1 2
1 3
1 2
1 3
5 6
3 4
2 5
1 2
1 3
1 2
1 3
3 5
1 2
1 3
1 4
5 7
4 5
3 4
2 3
1 2
1 6
1 2
5 6
5 8
3 7
2 3
2 5
1 2
1 4
5 6
4 5
2 4
2 7
1 2
1 3
5 7
...

result:

ok Accepted (10000 test cases)

Test #4:

score: 0
Accepted
time: 19ms
memory: 3624kb

input:

10000
10
2 6 7
2 8 4
1 8
0
1 9
1 10
1 9
1 10
0
0
10
3 2 8 5
4 3 9 7 10
0
1 8
0
1 9
0
0
0
0
9
2 2 5
3 3 7 6
0
1 7
2 8 9
0
0
0
0
3
2 2 3
0
0
6
3 4 3 6
1 4
0
0
1 6
0
10
3 2 4 7
2 10 8
1 10
0
1 8
1 9
1 9
0
0
0
3
1 3
1 3
0
5
2 5 4
1 5
1 4
0
0
2
1 2
0
9
3 2 3 7
0
4 5 6 8 9
1 5
0
0
0
0
0
6
4 2 3 4 6
0
0
0
...

output:

8 10
7 9
6 8
5 7
3 6
2 3
2 4
1 2
1 5
6 9
4 8
2 3
2 6
2 7
2 10
1 2
1 4
1 5
5 8
5 9
4 7
2 3
2 4
2 6
1 2
1 5
1 2
1 3
5 6
2 4
1 2
1 3
1 5
7 9
6 7
5 8
3 10
2 3
2 5
1 2
1 4
1 6
2 3
1 2
3 4
2 5
1 2
1 3
1 2
4 5
3 4
3 6
3 8
3 9
1 2
1 3
1 7
5 6
1 2
1 3
1 4
1 5
6 8
5 6
5 7
4 5
3 9
1 2
1 3
1 4
1 2
6 7
3 5
3 6
1...

result:

ok Accepted (10000 test cases)

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

16
392
4 2 3 165 13
0
2 4 12
0
4 177 7 9 23
2 187 16
0
1 13
0
1 13
2 208 27
0
2 14 22
0
1 23
2 19 20
1 208
3 21 25 27
0
0
0
0
0
2 208 29
0
2 32 31
3 44 40 38
1 208
0
1 44
0
3 35 49 52
1 42
2 36 208
0
0
1 44
1 42
1 49
1 60
2 79 213
0
3 46 79 57
2 47 48
1 60
0
0
0
0
1 213
1 79
1 64
1 57
2 79 63
2 62 2...

output:

389 391
386 389
385 387
384 388
383 392
382 390
380 385
379 382
378 386
377 380
377 383
377 384
376 381
373 375
373 378
372 373
371 376
370 379
367 374
367 377
364 367
364 368
364 369
364 370
364 372
362 363
362 364
361 371
358 360
358 366
357 365
356 357
356 362
354 358
353 359
353 361
350 354
349 ...

result:

wrong answer The index of the node i's father should less than i (test case 1)
English 繁體中文 简体中文

Server Time: 2025-03-05 12:47:59 | OpenSource Project