QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528589 | #6396. Puzzle: Kusabi | hnust_xiaoqi# | WA | 21ms | 12148kb | C++20 | 3.0kb | 2024-08-23 16:36:35 | 2024-08-23 16:36:37 |
Judging History
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.