QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471147#6396. Puzzle: KusabiUESTC_DebugSimulatorWA 22ms9624kbC++172.6kb2024-07-10 18:34:462024-07-10 18:34:47

Judging History

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

  • [2024-07-10 18:34:47]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:9624kb
  • [2024-07-10 18:34:46]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(i) (i&-i)
#define rand() (myrand())
using namespace std;
mt19937 myrand(time(0));
const int maxn = 2e5 + 5;
int n, _, head[maxn], cnt;
int c[maxn], dep[maxn], jud, fa[maxn];
string ty;
vector<pair<int, int> >ans;
struct node{
	int next, to;
}edge[maxn<<1];
void addedge(int from, int to) {
	edge[++cnt].next = head[from];
	edge[cnt].to = to;
	head[from] = cnt;
}
bool cmp(int x, int y) {return dep[x] < dep[y];}
int dfs(int u, int p) {
	if (jud) return 0;
	dep[u] = dep[p] + 1;
	vector<int>a[3];
	if (c[u] != -1) a[c[u]].push_back(u);
	for (int i = head[u] ; i ; i = edge[i].next) {
		int v = edge[i].to;
		if (v == p) continue;
		int x = dfs(v, u);
		if (c[x] != -1) a[c[x]].push_back(x);
	}
	sort(a[0].begin(), a[0].end(), cmp);
	sort(a[1].begin(), a[1].end(), cmp);
	sort(a[2].begin(), a[2].end(), cmp);
	int len0 = a[0].size(), len1 = a[1].size(), len2 = a[2].size(), res = 0, cnt = 0, pos = 0;
	while(pos < len0) {
		vector<int>stk;
		stk.push_back(a[0][pos]);
		while(pos + 1 < len0 && dep[a[0][pos + 1]] == dep[a[0][pos]]) {
			pos++;
			stk.push_back(a[0][pos]);
		}
		int tot = stk.size();
		if (tot >= 2) for (int i = 0 ; i < tot ; i += 2) {
			if (!stk[i] || !stk[i + 1]) continue;
			ans.push_back({stk[i], stk[i + 1]});
		}
		if (tot&1) {
			cnt++;
			res = stk[tot - 1];
		}
		pos++;
	}
	int i, j;
	if (len1 < len2) {
		for (i = len2 - 1, j = len1 - 1 ; i >= 0 && j >= 0 ; --i) {
			if (dep[a[1][j]] > dep[a[2][i]]) {
				ans.push_back({a[1][j], a[2][i]});
				j--;
			}
			else {
				res = a[2][i];
				cnt++;
			}
		}	
		if (!i) res = a[2][i], cnt++;
		if (!j) res = a[1][j], cnt++;
	}
	else {
		for (i = 0, j = 0 ; i < len1 && j < len2 ; ++i) {
			if (dep[a[1][i]] > dep[a[2][j]]) {
				ans.push_back({a[1][i], a[2][j]});
				j++;
			}
			else {
				res = a[1][i];
				cnt++;
			}
		}
		if (i == len1 - 1) res = a[1][i], cnt++;
		if (j == len2 - 1) res = a[2][j], cnt++;
	}
	if (cnt > 1) {
		jud = 1;
		return 0;
	}
	return res;
}
void solve() {
	cin >> n;
	for (int i = 0 ; i <= n ; ++i) c[i] = -1;
	for (int i = 1 ; i < n ; ++i) {
		int x, p;
		cin >> x >> p >> ty;
		fa[x] = p;
		if (ty[0] != '-') {
			if (ty[0] == 'T') c[x] = 0;
			if (ty[0] == 'C') c[x] = 1;
			if (ty[0] == 'D') c[x] = 2; 
		}
		addedge(x, p);
		addedge(p, x);
	}
	if (dfs(1, 0)) jud = 1;
	if (jud) {
		cout << "NO" << '\n';
		return;
	}
	cout << "YES" << '\n';
	for (auto [x, y] : ans) {
		cout << x << ' ' << y << '\n';
	}
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5748kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
8 6
5 4

result:

ok Correct.

Test #2:

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

input:

10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang

output:

YES
9 8
10 3
6 2
5 7

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 22ms
memory: 9624kb

input:

100000
2 1 Duan
3 1 Duan
4 3 -
5 4 Duan
6 3 -
7 4 Duan
8 4 -
9 8 -
10 7 Duan
11 9 -
12 7 Duan
13 7 Duan
14 8 Duan
15 13 -
16 10 Duan
17 11 Duan
18 12 -
19 1 Duan
20 5 Duan
21 4 Duan
22 14 Duan
23 16 -
24 22 Duan
25 16 Duan
26 13 -
27 13 -
28 17 -
29 5 Duan
30 22 -
31 23 -
32 9 Duan
33 5 -
34 30 Duan...

output:

YES
78961 61327
79617 28763
40169 25684
49361 25045
60228 24156
97603 50185
72206 56901
41848 10579
76635 73900
73042 50152
47346 25325
91464 63312
91034 79886
53651 27084
20428 10551
98200 36927
80157 69283
78977 68167
33135 10332
87866 40003
10826 10300
83126 81993
61240 63025
51469 32742
33688 26...

result:

wrong answer Vertex 9979 used twice.