QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528589#6396. Puzzle: Kusabihnust_xiaoqi#WA 21ms12148kbC++203.0kb2024-08-23 16:36:352024-08-23 16:36:37

Judging History

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

  • [2024-08-23 16:36:37]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:12148kb
  • [2024-08-23 16:36:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

const int N = 2e5 + 10;

typedef long long LL;

vector<pair<LL,LL>> duan[N],chang[N],tong[N];
char ch[N];
vector<LL> vec[N];
LL n;
LL inde_ans;
pair<LL,LL> ans[N];
bool flag=true;
void dfs(LL fa,LL pos,LL dp){
	if(ch[pos]=='T'){
		tong[pos].push_back({dp,pos});
	}else if(ch[pos]=='C'){
		chang[pos].push_back({dp,pos});
	}else if(ch[pos]=='D'){
		duan[pos].push_back({dp,pos});
	}
	for(LL i=vec[pos].size()-1;~i;--i){
		dfs(pos,vec[pos][i],dp+1);
		if(!flag) return;
	}
	LL sz=tong[pos].size(),dsz=duan[pos].size(),csz=chang[pos].size();
	if(abs(dsz-csz)>1||((sz&1)&&(dsz!=csz))){
		flag=false;
		return;
	}
	sort(tong[pos].begin(),tong[pos].end());
	sort(duan[pos].begin(),duan[pos].end());
	sort(chang[pos].begin(),chang[pos].end());
	bool f=true;
	LL i=0;
	while(i+1<sz){
		if(tong[pos][i].first==tong[pos][i+1].first){
			ans[++inde_ans]={tong[pos][i].second,tong[pos][i+1].second};
			i+=2;
		}else{
			if(f){
				tong[fa].push_back(tong[pos][i]);
				++i;
				f=false;
			}else{
				flag=false;
				return;
			}
		}
	}
	if(i<sz){
		if(f){
			tong[fa].push_back(tong[pos][i]);
			f=false;
		}else{
			flag=false;
			return;
		}
	}
	if(dsz==csz){
		for(LL i=0;i<csz;++i){
			if(duan[pos][i].first<chang[pos][i].first){
				ans[++inde_ans]={duan[pos][i].second,chang[pos][i].second};
			}else{
				flag=false;
				return;
			}
		}
	}else if(dsz<csz){
		LL i,k;
		for(i=0,k=0;i<dsz;++i,++k){
			if(duan[pos][i].first<chang[pos][k].first){
				ans[++inde_ans]={duan[pos][i].second,chang[pos][k].second};
			}else{
				if(f){
					f=false;
					chang[fa].push_back(chang[pos][k]);
					--i;
				}else{
					flag=false;
					return;
				}
			}
		}
		if(k<csz){
			if(f){
				f=false;
				chang[fa].push_back(chang[pos][k]);
				--i;
			}else{
				flag=false;
				return;
			}
		}
	}else{
		LL i,k;
		for(i=csz-1,k=dsz-1;~i;--i,--k){
			if(chang[pos][i].first>duan[pos][k].first){
				ans[++inde_ans]={duan[pos][k].second,chang[pos][i].second};
			}else{
				if(f){
					f=false;
					duan[fa].push_back(duan[pos][k]);
				}else{
					flag=false;
					return;
				}
			}
		}
		if(k<dsz){
			if(f){
				f=false;
				duan[fa].push_back(duan[pos][k]);
			}else{
				flag=false;
				return;
			}
		}
	}
	// cout<<pos<<' '<<tong[pos].size()<<' '<<chang[pos].size()<<' '<<duan[pos].size()<<endl;
	
}
void solve() {
	cin >> n;
	if(n==1){
		cout<<"YES"<<endl;
		return;
	}
	for(int i = 1; i < n; i++) {
		LL data,data2;
		string str;
		cin>>data>>data2>>str;
		vec[data2].push_back(data);
		ch[data]=str[0];
	}
	dfs(0,1,0);
	if(flag&&!duan[0].size()&&!chang[0].size()&&!tong[0].size()){
		cout<<"YES"<<endl;
		for(LL i=1;i<=inde_ans;++i){
			cout<<ans[i].first<<' '<<ans[i].second<<endl;
		}
	}else{
		cout<<"NO"<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7672kb

input:

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

output:

YES
6 8
4 5

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 21ms
memory: 12148kb

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.