QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103719#6396. Puzzle: KusabitarjenWA 64ms39244kbC++172.3kb2023-05-07 13:24:222023-05-07 13:24:25

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:24:25]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:39244kb
  • [2023-05-07 13:24:22]
  • 提交

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;
    vector<int> v,t;
    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;
        if(s!="-")v.push_back(i);
    }
    // cout<<"cnt="<<cnt<<"\n";
    dfs(1,0);
    cout<<"YES\n";
    for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n",t.push_back(x),t.push_back(y);
    sort(t.begin(),t.end());
    sort(v.begin(),v.end());
    // for(auto it:v)cout<<it<<" ";;cout<<"\n";
    // for(auto it:t)cout<<it<<" ";;cout<<"\n";
    assert(t==v);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 17ms
memory: 36944kb

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: 13ms
memory: 37016kb

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: 0
Accepted
time: 13ms
memory: 36968kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 64ms
memory: 39244kb

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.