QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234792#5545. Contingency Plandmmm#TL 3ms9876kbC++141.7kb2023-11-01 22:30:532023-11-01 22:30:53

Judging History

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

  • [2023-11-01 22:30:53]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:9876kb
  • [2023-11-01 22:30:53]
  • 提交

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);
}
vector<int> getsome(int u) {
	int cnt = 20;
	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);
	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: 9024kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

4 1
1 3
2 5
3 5

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 5
3 1
4 2
2 3

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 4
1 3
3 2
3 5

result:

ok AC

Test #7:

score: -100
Time Limit Exceeded

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:


result: