QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234799#5545. Contingency Plandmmm#WA 41ms14188kbC++141.7kb2023-11-01 22:38:262023-11-01 22:38:26

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 22:38:26]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:14188kb
  • [2023-11-01 22:38:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxN = 1e5 + 69;
struct vl {
	int x, y;
	size_t operator() (const vl& p) const {
		return (p.x << 32) ^ p.y;
	}
	bool operator == (const vl& oth) const {
		return x == oth.x && y == oth.y;
	}
};
int n;
int u[maxN], v[maxN];
unordered_set<vl, vl> us;
set<int> adj[maxN];
mt19937 rng(time(NULL));
void dfs(int u, int p, vector<int>& res, int& cnt) {
	res.push_back(u);
	cnt--;
	if (cnt <= 0) return;
	for (int v : adj[u])
	if (v != p) {
		dfs(v, u, res, cnt);
		if (cnt <= 0) return;
	}
}
vector<int> getsome(int u) {
	int cnt = 50;
	vector<int> res;
	dfs(u, u, res, cnt);
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	us.reserve(maxN * 2);
	for (int i = 1; i <= n - 1; i++) {
		cin >> u[i] >> v[i];
		adj[u[i]].insert(v[i]);
		adj[v[i]].insert(u[i]);
		us.insert({min(u[i], v[i]), max(u[i], v[i])});
	} 
	vector<int> ans;
	for (int i = 1; i <= n - 1; i++) {
		if (adj[u[i]].size() <= 1 && adj[v[i]].size() <= 1)
			return cout << -1, 0;
		adj[u[i]].erase(v[i]);
		adj[v[i]].erase(u[i]);

		vector<int> lolu = getsome(u[i]);
		vector<int> lolv = getsome(v[i]);
		shuffle(lolu.begin(), lolu.end(), rng);
		shuffle(lolv.begin(), lolv.end(), rng);
		
		int xu = -1, xv;
		for (int yu : lolu)
		for (int yv : lolv)
		if (!us.count({min(yu, yv), max(yu, yv)})) {
			xu = yu;
			xv = yv;
			goto flag;
		}
		flag:;
		if (xu == -1) {
			return cout << -1, 0;
		}

		adj[xu].insert(xv);
		adj[xv].insert(xu);
		ans.push_back(xu);
		ans.push_back(xv);
		// cout << xu << ' ' << xv << '\n';
	}
	for (int i = 0; i < ans.size(); i += 2)
		cout << ans[i] << ' ' << ans[i + 1] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

7
1 2
3 7
2 4
2 5
1 3
3 6

output:

3 2
2 7
7 4
4 5
1 4
5 6

result:

ok AC

Test #2:

score: 0
Accepted
time: 0ms
memory: 9564kb

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 3ms
memory: 10956kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: 0
Accepted
time: 0ms
memory: 10152kb

input:

5
2 1
2 3
2 4
4 5

output:

3 1
4 1
2 5
3 5

result:

ok AC

Test #5:

score: 0
Accepted
time: 3ms
memory: 9888kb

input:

5
1 4
3 4
4 5
2 5

output:

1 3
3 5
4 2
2 3

result:

ok AC

Test #6:

score: 0
Accepted
time: 0ms
memory: 9524kb

input:

5
5 2
1 2
4 2
3 4

output:

5 1
1 4
3 2
3 1

result:

ok AC

Test #7:

score: 0
Accepted
time: 35ms
memory: 13228kb

input:

20000
1 2
1 3
4 1
5 1
6 1
7 1
1 8
1 9
1 10
1 11
12 1
1 13
14 1
1 15
1 16
17 1
1 18
1 19
20 1
21 1
22 1
1 23
24 1
1 25
26 1
1 27
28 1
29 1
30 1
1 31
1 32
1 33
1 34
1 35
36 1
1 37
1 38
1 39
40 1
41 1
1 42
1 43
44 1
1 45
46 1
1 47
48 1
49 1
1 50
1 51
52 1
53 1
54 1
1 55
56 1
57 1
58 1
1 59
60 1
61 1
1 ...

output:

13 2
24 3
4 31
5 40
6 18
7 18
14 8
45 9
19 10
21 11
12 42
34 2
8 42
27 15
45 16
17 12
46 6
48 10
20 4
11 13
22 50
15 23
24 15
33 25
26 45
42 15
28 8
29 5
30 14
18 20
48 32
36 33
41 21
19 35
36 45
35 37
32 38
25 39
29 50
34 19
18 24
39 43
44 25
51 26
4 41
29 47
7 78
49 9
57 29
59 51
52 40
53 66
54 73...

result:

ok AC

Test #8:

score: 0
Accepted
time: 36ms
memory: 14188kb

input:

20000
7662 1
9205 1
5971 1
1 9886
1 18853
14108 1
998 1
1 14958
7100 1
1 2670
1 18493
13838 1
4644 1
2139 1
1 18540
1 14081
1 16836
1 9357
245 1
242 1
1 13472
1 1471
3792 1
1 17875
13976 1
1 15085
1 17283
15014 1
17477 1
11578 1
18441 1
1 14367
3018 1
1 7186
1 4939
2470 1
2993 1
6175 1
1 19886
1 125...

output:

7662 12
9205 22
5971 28
36 9886
13 18853
14108 7662
998 8
37 14958
7100 7662
14108 2670
32 18493
13838 9205
4644 8
2139 5
35 18540
32 14081
34 16836
35 9357
245 12
242 7
8 13472
242 1471
3792 7
2670 17875
13976 242
21 15085
17875 17283
15014 17875
17477 15
11578 13
18441 15085
19 14367
3018 7100
172...

result:

ok AC

Test #9:

score: -100
Wrong Answer
time: 41ms
memory: 13152kb

input:

20000
8854 1
15635 1
8088 1
1 12138
12367 1
1 15051
6392 1
15564 1
17334 1
1 10164
8704 1
1 13795
1 10292
12108 1
1 50
4 1
1 18364
13341 1
19203 1
1 3017
1 5133
3499 1
19202 1
1 10304
12975 1
1 17220
1 1716
1 4158
1 16763
1 301
1 16645
8690 1
1 10064
16977 1
1 19618
1 5471
1 8763
3997 1
1 3283
11332...

output:

-1

result:

wrong output format Unexpected end of file - int32 expected