QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528403 | #6396. Puzzle: Kusabi | hnust_xiaoqi# | RE | 2ms | 9764kb | C++20 | 1.9kb | 2024-08-23 13:34:22 | 2024-08-23 13:34:22 |
Judging History
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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