QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#234802#5545. Contingency Plandmmm#WA 127ms13352kbC++141.7kb2023-11-01 22:40:122023-11-01 22:40:13

Judging History

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

  • [2023-11-01 22:40:13]
  • 评测
  • 测评结果:WA
  • 用时:127ms
  • 内存:13352kb
  • [2023-11-01 22:40:12]
  • 提交

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 = 300;
	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';
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10208kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 2ms
memory: 10020kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: 0
Accepted
time: 2ms
memory: 10964kb

input:

5
2 1
2 3
2 4
4 5

output:

3 1
4 3
2 5
1 5

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 3
3 2
4 2
1 5

result:

ok AC

Test #6:

score: 0
Accepted
time: 2ms
memory: 9628kb

input:

5
5 2
1 2
4 2
3 4

output:

5 1
1 3
3 2
5 4

result:

ok AC

Test #7:

score: 0
Accepted
time: 127ms
memory: 13352kb

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:

230 2
16 3
4 289
5 187
6 194
7 264
162 8
71 9
59 10
179 11
12 162
205 13
14 138
251 15
234 3
17 163
197 18
119 19
20 244
21 231
22 107
108 23
24 100
78 25
26 41
94 27
28 207
29 237
30 21
140 31
175 32
47 33
217 34
252 35
36 129
190 37
69 38
86 39
40 298
26 270
268 42
300 43
44 234
78 45
46 204
30 33...

result:

ok AC

Test #8:

score: -100
Wrong Answer
time: 124ms
memory: 13316kb

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