QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244115#7738. Equivalent RewritingTJUHuangTaoRE 1ms3528kbC++201.6kb2023-11-08 21:19:462023-11-08 21:19:47

Judging History

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

  • [2023-11-08 21:19:47]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3528kb
  • [2023-11-08 21:19:46]
  • 提交

answer

#include<bits/stdc++.h>
//#define int long long
//#pragma GCC optimize(3,"Ofast","inline")//bitset配合用
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int,int>
#define db double
using namespace std;
const int maxn=1e2+10;
int top[maxn],in[maxn],dep[maxn];
vector<int>v[maxn];
vector<int>G[maxn];
vector<int>ans[maxn];
void solve(){
    priority_queue<int>q;
    int n,m;cin>>n>>m;
    swap(n,m);
    for(int i=0;i<=m;i++) in[i]=0,dep[i]=0,v[i].clear(),G[i].clear(),ans[i].clear();
    for(int i=1;i<=m;i++){
        int len;cin>>len;
        for(int j=1;j<=len;j++){
            int tem;cin>>tem;
            v[i].push_back(tem);
            top[tem]=i;
        }
    }
    for(int i=1;i<=m;i++){
        for(auto it:v[i]){
            if(top[it]!=i){
                in[top[it]]++;
                G[i].push_back(top[it]);
            }
        }
    }
    int flag=0;
    for(int i=1;i<=m;i++){
        if(!in[i]) q.push(i);
    }
    while(!q.empty()){
        int u=q.top();q.pop();
        ans[dep[u]].push_back(u);
        if(ans[dep[u]].size()>1) flag=1;
        for(auto v:G[u]){
            in[v]--;
            if(!in[v]){
                q.push(v);
                dep[v]=dep[u]+1;
            }
        }
    }
    if(!flag){cout<<"No"<<endl;return;}
    cout<<"Yes"<<endl;
    for(int i=0;i<=m;i++){
        for(auto it:ans[i]) cout<<it<<" ";
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    //system("pause");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3528kb

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:

Yes
3 1 2 
No
No

result:

ok OK. (3 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3432kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

Yes
8 7 6 5 4 3 2 1 9 10 

result:

ok OK. (1 test case)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

1
20 5
5 4 1 2 5 3
2 5 3
3 5 1 2
5 4 5 1 3 2
3 4 2 5
5 3 1 5 4 2
5 5 1 2 3 4
1 3
4 5 1 2 3
4 4 1 3 5
2 5 2
4 2 3 5 1
3 2 4 5
5 2 3 4 1 5
4 5 2 4 3
1 2
2 4 3
4 4 5 3 1
5 4 1 5 3 2
3 5 1 3

output:

Yes
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 19 20 

result:

ok OK. (1 test case)

Test #4:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

1
40 10
2 4 1
10 5 8 2 3 6 7 4 1 10 9
3 10 9 7
1 9
10 10 5 6 9 2 8 3 1 4 7
7 8 4 7 5 2 3 6
5 2 6 5 1 10
6 6 5 4 8 7 1
3 4 9 8
9 9 10 4 2 1 8 7 5 3
2 5 7
9 8 6 1 2 9 7 5 10 3
2 8 1
8 8 3 10 9 1 4 5 6
2 3 4
5 5 3 6 2 7
10 3 2 8 9 10 1 7 4 6 5
2 1 9
1 1
3 3 7 4
5 2 6 5 7 1
7 3 2 4 9 10 6 1
1 4
5 6 4 5 ...

output:

Yes
36 35 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 34 39 38 37 40 

result:

ok OK. (1 test case)

Test #5:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

1
100 20
12 10 5 11 13 12 14 7 15 19 18 3 1
10 16 11 19 8 10 15 5 12 13 14
12 16 8 11 15 2 18 14 13 20 4 12 7
10 3 9 1 7 19 6 2 14 8 20
7 17 18 20 3 9 6 10
4 1 4 19 9
13 14 17 16 11 13 8 10 19 18 7 5 20 1
13 10 15 3 2 9 1 17 7 20 13 19 18 16
2 17 9
10 20 19 13 14 16 17 8 12 18 15
5 2 16 14 6 19
1 14...

output:

Yes
98 96 95 94 93 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 92 99 97 100 

result:

ok OK. (1 test case)

Test #6:

score: -100
Runtime Error

input:

1
5000 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:


result: