QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234865#5545. Contingency Plandmmm#TL 3ms10148kbC++141.8kb2023-11-02 00:26:182023-11-02 00:26:18

Judging History

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

  • [2023-11-02 00:26:18]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:10148kb
  • [2023-11-02 00:26:18]
  • 提交

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) {
	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], n);
		vector<int> lolv = getsome(v[i], n / lolu.size() + 1);
		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: 3ms
memory: 9804kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

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

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

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

input:

5
2 1
2 3
2 4
4 5

output:

4 1
1 3
2 5
1 5

result:

ok AC

Test #5:

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

input:

5
1 4
3 4
4 5
2 5

output:

1 5
3 2
4 2
3 5

result:

ok AC

Test #6:

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

input:

5
5 2
1 2
4 2
3 4

output:

5 4
1 5
3 2
3 1

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: