QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#528403#6396. Puzzle: Kusabihnust_xiaoqi#RE 2ms9764kbC++201.9kb2024-08-23 13:34:222024-08-23 13:34:22

Judging History

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

  • [2024-08-23 13:34:22]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:9764kb
  • [2024-08-23 13:34:22]
  • 提交

answer

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

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;
typedef pair<int, int> PII;
const LL LLF=1e18;

pair<LL,LL> duan[N],chang[N],tong[N];
char ch[N];
bool flag[N];
vector<LL> vec[N];
LL n;
LL inde_duan,inde_chang,inde_tong;
void dfs(LL pos,LL dp){
	if(ch[pos]=='T'){
		tong[++inde_tong]={pos,dp};
	}else if(ch[pos]=='C'){
		chang[++inde_chang]={pos,dp};
	}else if(ch[pos]=='D'){
		duan[++inde_duan]={pos,dp};
	}
	for(LL i=vec[pos].size()-1;~i;--i){
		dfs(vec[pos][i],dp+1);
	}
}
bool check(){
	if(inde_chang!=inde_duan||(inde_tong&1)) return false;
	for(LL i=1;i<=inde_tong;i+=2){
		if(tong[i].second!=tong[i+1].second){
			return false;
		}
	}
	for(LL i=1;i<=inde_duan;++i){
		if(duan[i].second>=chang[i].second){
			return false;
		}
	}
	return true;
}
void solve() {
	cin >> n;
	flag[1]=true;
	for(int i = 1; i < n; i++) {
		LL data,data2;
		string str;
		cin>>data>>data2>>str;
		if(flag[data]){
			vec[data].push_back(data2);
			ch[data2]=str[0];
			flag[data2]=true;
		}else{
			vec[data2].push_back(data);
			ch[data]=str[0];
			flag[data]=true;
		}
	}
	dfs(1,0);
	sort(tong+1,tong+inde_tong,[&](const auto& a,const auto &b){
		return a.second<b.second;
	});
	sort(duan+1,duan+inde_duan,[&](const auto& a,const auto &b){
		return a.second<b.second;
	});
	sort(chang+1,chang+inde_chang,[&](const auto& a,const auto &b){
		return a.second<b.second;
	});
	if(check()){
		cout<<"YES"<<endl;
		for(LL i=1;i<=inde_tong;i+=2){
			cout<<tong[i].first<<' '<<tong[i+1].first<<endl;
		}
		for(LL i=1;i<=inde_duan;++i){
			cout<<duan[i].first<<' '<<chang[i].first<<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();
	}
}

詳細信息

Test #1:

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

input:

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

output:

YES
5 4
6 8

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

score: -100
Runtime Error

input:

2
2 1 Tong

output:


result: