QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471008#6396. Puzzle: KusabiUESTC_DebugSimulatorWA 15ms9880kbC++173.5kb2024-07-10 17:13:082024-07-10 17:13:09

Judging History

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

  • [2024-07-10 17:13:09]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:9880kb
  • [2024-07-10 17:13:08]
  • 提交

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], use[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;
	for (int i = head[u] ; i ; i = edge[i].next) {
		int v = edge[i].to, x;
		if (v == p) continue;
		x = dfs(v, u);
		if (x) a.push_back(x);
	}
	sort(a.begin(), a.end(), cmp);
	int pos = 0, len = a.size(), res = 0;
	if (!c[u]) res = u;
	while(pos < len) {
		vector<int>stk;
		stk.push_back(a[pos]);
		while(pos + 1 < len && dep[a[pos + 1]] == dep[a[pos]]) {
			pos++;
			stk.push_back(a[pos]);
		}
		int tot = stk.size();
		if (tot >= 2) for (int i = 0 ; i < tot ; i += 2) ans.push_back({stk[i], stk[i + 1]});
		if (tot&1) {
			if (res) {
				jud = 1;
				return 0;
			}
			res = stk[tot - 1];
		}
		pos++;
	}
	return res;
}
int dfs1(int u, int p) {
	if (jud) return 0;
	vector<int>a[2];
	if (c[u] > 0) a[c[u] - 1].push_back(u);
	for (int i = head[u] ; i ; i = edge[i].next) {
		int v = edge[i].to, x;
		if (dep[v] < dep[u] || use[v]) continue;
		x = dfs1(v, u);
		if (x && c[x] > 0) a[c[x] - 1].push_back(x);
	}
	sort(a[0].begin(), a[0].end(), cmp);
	sort(a[1].begin(), a[1].end(), cmp);
	int len0 = a[0].size(), len1 = a[1].size(), res = 0, i, j, cnt = 0;
	if (a[0].size() < a[1].size()) {
		priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
		for (i = len1 - 1, j = len0 - 1 ; i >= 0 ; i--) {
			while(j >= 0 && dep[a[0][j]] > dep[a[1][i]]) {
				q.push({dep[a[0][j]], a[0][j]});
				j--;
			}
			if (q.empty()) {
				cnt++;
				res = a[1][i];
				continue;
			}
			pair<int, int>t;
			t = q.top();q.pop();
			ans.push_back({t.second, a[1][i]});
		}	
		swap(i, j);	
		if (!i) res = a[0][i], cnt++;
		if (!j) res = a[1][j], cnt++;
		cnt += q.size();
	}
	else {
		priority_queue<pair<int, int> >q;
		for (i = 0, j = 0 ; i < len0 ; i++) {
			while(j < len1 && dep[a[0][i]] > dep[a[1][j]]) {
				q.push({dep[a[1][j]], a[1][j]});
				j++;
			}
			if (q.empty()) {
				cnt++;
				res = a[0][i];
				continue;
			}
			pair<int, int>t;
			t = q.top();q.pop();
			ans.push_back({a[0][i], t.second});
		}
		if (i == len0 - 1) res = a[0][i], cnt++;
		if (j == len1 - 1) res = a[1][j], cnt++;
		cnt += q.size();
	}
	if (cnt > 1) return 0;
	return res;
}
void solve() {
	cin >> n;
	for (int i = 1 ; 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;
	for (auto [x, y] : ans) {
		while(x != y) {
			use[x] = 1, x = fa[x];
			use[y] = 1, y = fa[y];
		}
	}
	use[1] = 1;
	for (int i = 1 ; i <= n ; ++i) {
		if (use[i]) {
			if (dfs1(i, 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
5 4
8 6

result:

ok Correct.

Test #2:

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

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: 1ms
memory: 7800kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 15ms
memory: 9880kb

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:

NO

result:

wrong answer Jury has answer but participant has not.