QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234800#5545. Contingency Plandmmm#WA 46ms13880kbC++141.7kb2023-11-01 22:39:162023-11-01 22:39:16

Judging History

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

  • [2023-11-01 22:39:16]
  • 评测
  • 测评结果:WA
  • 用时:46ms
  • 内存:13880kb
  • [2023-11-01 22:39:16]
  • 提交

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 = 100;
	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: 9644kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

5 1
1 3
2 5
4 1

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 2
3 1
4 2
1 5

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 3
1 5
3 2
5 4

result:

ok AC

Test #7:

score: 0
Accepted
time: 46ms
memory: 13880kb

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:

76 2
56 3
4 10
5 39
6 34
7 69
31 8
32 9
18 10
74 11
12 64
10 13
14 19
78 15
18 16
17 85
8 10
75 19
20 41
21 96
22 76
70 23
24 93
37 25
26 61
93 27
28 95
29 3
30 66
11 13
65 9
53 33
14 34
22 35
36 63
92 37
83 38
73 39
40 81
20 62
31 42
99 43
44 36
93 45
46 56
97 47
48 89
49 63
20 50
11 51
52 25
33 57...

result:

ok AC

Test #8:

score: -100
Wrong Answer
time: 45ms
memory: 13564kb

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:

-1

result:

wrong output format Unexpected end of file - int32 expected