QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477008#5545. Contingency Plankaruna#WA 1ms3568kbC++201.2kb2024-07-13 22:21:582024-07-13 22:21:58

Judging History

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

  • [2024-07-13 22:21:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3568kb
  • [2024-07-13 22:21:58]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int SZ = 101010;

int n, u[SZ], v[SZ], deg[SZ];
vector<int> g[SZ];

int dep[SZ], par[SZ];
void dfs(int p, int v) {
	for (int x : g[v]) if (p != x) {
		dep[x] = dep[v] + 1;
		par[x] = v;
		dfs(v, x);
	}
}
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> u[i] >> v[i];
		deg[u[i]]++;
		deg[v[i]]++;
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}

	for (int i = 1; i <= n; i++) if (deg[i] == n - 1) return !(cout << "-1\n");

	int pos = -1;
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1 && i != u[0] && i != v[0]) {
			pos = i;
			break;
		}
	}
	if (pos == -1) return !(cout << "-1\n");

	dfs(-1, pos);

	vector<pii> V;

	for (int i = 0; i < n - 1; i++) {
		if (dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);

		if (u[i] == pos) {
			int x = max_element(dep + 1, dep + 1 + n) - dep;
			V.push_back({v[i], x});
		}
		else {
			V.push_back({pos, v[i]});
		}
	}

	for (auto [u, v] : V) {
		cout << u << ' ' << v << '\n';
	}

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

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

output:

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

result:

ok AC

Test #2:

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

input:

3
1 2
2 3

output:

-1

result:

ok AC

Test #3:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

2
2 1

output:

-1

result:

ok AC

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3568kb

input:

5
2 1
2 3
2 4
4 5

output:

3 1
2 5
3 4
3 5

result:

wrong answer cycle detected