QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103908#6396. Puzzle: KusabijccccWA 23ms7632kbC++172.9kb2023-05-07 20:18:402023-05-07 20:18:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 20:18:44]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:7632kb
  • [2023-05-07 20:18:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int N = 1e6 + 10;
const int M = 131;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;

void solve(){
	int n; cin >> n;
	vector<int> val(n + 1);
	vector<vector<int>> g(n + 1);
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		g[b].push_back(a);
		string s; cin >> s;
		if(s == "-") continue;
		if(s == "Tong") val[a] = 3;
		else if(s == "Duan") val[a] = 1;
		else val[a] = 2;
	}
	int flag = 1;
	vector<PII> res;
	vector<int> dep(n + 1);
	
	function <void(int)> dfs1 = [&] (int u){
		for(int v : g[u]){
			dep[v] = dep[u] + 1;
			dfs1(v);
		}	
	};
	
	function <int(int)> dfs2 = [&] (int u) -> int{
		vector<int> aa, bb, cc;
		for(int v : g[u]){
			int num = dfs2(v);
			if(!flag) return 0;
			if(num == 0) continue;
			if(val[num] == 1) aa.push_back(num);
			if(val[num] == 2) bb.push_back(num);
			if(val[num] == 3) cc.push_back(num);
		}
		if(val[u] == 1) aa.push_back(u);
		if(val[u] == 2) bb.push_back(u);
		if(val[u] == 3) cc.push_back(u);
		sort(aa.begin(), aa.end(), [&] (int a, int b){
			return dep[a] < dep[b];
			});
		sort(bb.begin(), bb.end(), [&] (int a, int b){
			return dep[a] < dep[b];
			});
		sort(cc.begin(), cc.end(), [&] (int a, int b){
			return dep[a] < dep[b];
			});
		vector<int> num;
		int k = 0, z = cc.size();
		for(;k < z - 1; k += 2){
			if(dep[cc[k]] == dep[cc[k + 1]]){
				res.push_back({cc[k], cc[k + 1]});
				continue;
			}
			num.push_back(cc[k]);
			k--;
		}
		while(k < cc.size()) num.push_back(cc[k]), k++;
		
		if(aa.size() > bb.size()){
			int i = 0, j = 0;
			for(; i < aa.size() && j < bb.size();){
				if(dep[aa[i]] >= dep[bb[j]]){
					num.push_back(aa[i]);
					i++;
				}
				else res.push_back({aa[i], bb[j]}), i++, j++;
			}
			while(i < aa.size()) num.push_back(aa[i]), i++;
			while(j < bb.size()) num.push_back(bb[i]), j++;
		}
		else{
			int i = 0, j = 0;
			for(; i < aa.size() && j < bb.size();){
				if(dep[aa[i]] >= dep[bb[j]]){
					num.push_back(bb[j]);
					j++;
				}
				else res.push_back({aa[i], bb[j]}), i++, j++;
			}
			while(i < aa.size()) num.push_back(aa[i]), i++;
			while(j < bb.size()) num.push_back(bb[i]), j++;
		}
		if(num.size() >= 2){
			flag = 0;
			return 0;
		}
		return (num.size() ? num[0] : 0);
	};
	
	dep[1] = 1;
	dfs1(1);
	int num = dfs2(1);
	if(num != 0) flag = 0;
	if(!flag) cout << "NO" << endl;
	else{
		cout << "YES" << endl;
		for(auto [id1, id2] : res) cout << id1 << ' ' << id2 << endl;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(12);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	return 0 - 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
4 5
6 8

result:

ok Correct.

Test #2:

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

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
3 10
8 9
2 6
7 5

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 23ms
memory: 7632kb

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.