QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103721#6396. Puzzle: KusabitarjenWA 8ms37012kbC++172.0kb2023-05-07 13:39:552023-05-07 13:39:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 13:39:59]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:37012kb
  • [2023-05-07 13:39:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
vector<pair<int,int>> ans;
void no(){
    // for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
    cout<<"NO\n";exit(0);
}

set<int> s[3][maxn];
vector<int> ve[maxn];
int typ[maxn],dep[maxn];
int n;
void dfs(int x,int h){
    // cout<<"x="<<x<<" h="<<h<<"\n";
    dep[x]=dep[h]+1;
    set<int> now[3];
    for(auto it:ve[x]){
        dfs(it,x);
        for(int z=0;z<3;z++){
            for(auto it:s[z][it])now[z].insert(it);
        }
    }
    if(typ[x]!=-1)now[typ[x]].insert(x);
    map<int,int> ma;
    for(auto it:now[0]){
        if(ma.find(dep[it])!=ma.end()){
            ans.emplace_back(ma[dep[it]],it);
            ma.erase(dep[it]);
        }
        else ma[dep[it]]=it;
    }
    int res0=-1;
    if(ma.size()>0)res0=ma.begin()->second;
    set<pair<int,int>> s1,s2;
    for(auto it:now[1])s1.insert({dep[it],it});
    for(auto it:now[2])s2.insert({dep[it],it});
    auto it2=s1.end();
    while(it2!=s1.begin()){
        it2--;
        auto [d,x]=*it2;
        auto fd=s2.lower_bound({d+1,0});
        if(fd==s2.end()){
            it2--;continue;
        }
        ans.emplace_back(x,fd->second);
        s2.erase(fd);
        it2=s1.erase(it2);
    }
    // if((int)ma.size()+(int)s1.size()+(int)s2.size()>1)no();
    if(res0!=-1)s[0][x].insert(res0);
    if(!s1.empty())s[1][x].insert(s1.begin()->second);
    if(!s2.empty())s[2][x].insert(s2.begin()->second);
    // if(x==1){
    //     if((int)ma.size()+(int)s1.size()+(int)s2.size()>0)no();
    // }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    memset(typ,-1,sizeof(typ));
    cin>>n;
    for(int i=2;i<=n;i++){
        int x;cin>>x>>x;
        string s;
        cin>>s;
        ve[x].push_back(i);
        if(s=="Tong")typ[i]=0;
        if(s=="Duan")typ[i]=1;
        if(s=="Chang")typ[i]=2;
    }
    dfs(1,0);
    cout<<"YES\n";
    for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 36940kb

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: 3ms
memory: 36952kb

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

result:

ok Correct.

Test #3:

score: -100
Wrong Answer
time: 8ms
memory: 37012kb

input:

2
2 1 Tong

output:

YES

result:

wrong answer Only odd number of marked vertices to match.