QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246528#7738. Equivalent RewritingtrigriffinWA 1ms6304kbC++141.8kb2023-11-10 21:43:502023-11-10 21:43:50

Judging History

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

  • [2023-11-10 21:43:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6304kb
  • [2023-11-10 21:43:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int las[110000],in[110000];
vector<int>G[110000];
int ans[110000];
int n,m;
bool topu(){
    deque<int>q;
    int cnt=0;
    bool flag=0;
    int k=0;
    for(int i=n;i>=1;i--){
        if(!in[i]) {k++;q.push_back(i);}
    }
    if(k>1) flag=1;
    while(q.size()){
        int now=q.front();
        cout<<now<<endl;
        ans[++cnt]=now;
        q.pop_front();
        int tot=0;
        vector<int>a;
        for(auto nxt:G[now]){
            in[nxt]--;
            if(!in[nxt]) {tot++;a.push_back(nxt);}
        }
        if(tot){
            sort(a.begin(),a.end());
            reverse(a.begin(),a.end());
            if(tot>1) flag=1;
            for(auto el:a) {q.push_back(el);}
        }
    }
    return flag;
}
void solve(){
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) las[i]=0,G[i].clear(),in[i]=0;
    vector<int>b[n+5];
    for(int i=1;i<=n;i++){
        int p;
        scanf("%d",&p);
        b[i].resize(p+1);
        b[i][0]=p;
        for(int j=1;j<=p;j++){
            scanf("%d",&b[i][j]);
            las[b[i][j]]=i;
        }
        // sort(b[i].begin()+1,b[i].end());
    }
    for(int i=1;i<=n;i++){
        map<int,bool>ex;
        // cout<<i<<" "<<b[i][0]<<endl;
        for(int j=1;j<=b[i][0];j++){
            // cout<<j<<" ";
            int nxt=las[b[i][j]];
            if(!nxt) continue;
            if(ex[nxt]||nxt==i) continue;
            G[i].push_back(nxt);
            in[nxt]++;
        }
    }
    if(!topu()){
        puts("No");
        return;
    }
    puts("Yes");
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    puts("");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6304kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

3
1
2
Yes
3 1 2 
1
2
No
1
No

result:

wrong answer Token parameter [name=yesno] equals to "3", doesn't correspond to pattern "Yes|No" (test case 1)