QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#251987#6396. Puzzle: Kusabiucup-team1074WA 27ms8548kbC++202.2kb2023-11-15 14:06:102023-11-15 14:06:12

Judging History

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

  • [2023-11-15 14:06:12]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:8548kb
  • [2023-11-15 14:06:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define list sajioaw
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
int a[N];
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
vector<int>list[3];
vector<int>tr[N];
int depth[N];
void dfs(){
	queue<int>q;
	q.push(1);
	depth[1] = 1;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(auto it : tr[x]){
			depth[it] = depth[x] + 1;
			q.push(it);
		}
	}
}
int cmp(int a , int b){
	return depth[a] < depth[b];
}
int cmp2(int a , int b){
	return depth[a] > depth[b];
}
void solve() 
{
	cin >> n;
	for(int i = 0 ;i < n ; i ++){
		int ch , fa ;
		string s;
		cin >> ch >> fa >> s;
		tr[fa].pb(ch);
		if(s == "Tong"){
			list[0].pb(ch);
		}
		else if(s == "Duan"){
			list[1].pb(ch);
		}
		else if(s == "Chang"){
			list[2].pb(ch);
		}
	}
	dfs();
	vector<pair<int , int > > v;
	sort(list[0].begin() , list[0].end() , cmp);
	if(list[0].size() % 2 == 1){
		cout<<"NO\n";
		return;
	}
	else{
		for(int i = 0 ; i < list[0].size() ; i += 2){
			int x = list[0][i] , y = list[0][i + 1];
			if(depth[x] == depth[y]){
				v.pb({x , y});
			}
			else{
				cout<<"NO\n";
				return;
			}
		}
	}
	sort(list[1].begin() , list[1].end() , cmp);
	sort(list[2].begin() , list[2].end() , cmp);
	if(list[1].size() != list[2].size()){
		cout<<"NO\n";
		return;
	}
	else{
		for(int i = 0 ; i < list[1].size() ; i ++){
			int x = list[1][i] , y = list[2][i];
			if(depth[x] < depth[y]){
				v.pb({x , y});				
			}
			else{
				cout<<"NO\n";
				return;				
			}
		}
	}
	cout<<"YES\n";
	for(auto it : v){
		cout<<it.x<<" "<<it.y<<endl;
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

详细

Test #1:

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

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: 0ms
memory: 5848kb

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 27ms
memory: 8548kb

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
3283 78400
8241 93895
28194 69010
59851 85932
52589 27446
31315 7241
69894 83333
58699 33789
15911 19874
3681 24772
41090 95031
8873 3156
79799 14132
87751 74813
28273 85594
53651 61413
27407 11158
61255 27084
2042 86323
60707 54276
41654 35332
8051 63173
35912 79826
5203...

result:

wrong answer Edge 4707-66 used twice.