QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#244116#7738. Equivalent RewritingTJUHuangTaoWA 23ms16400kbC++201.6kb2023-11-08 21:20:072023-11-08 21:20:07

Judging History

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

  • [2023-11-08 21:20:07]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:16400kb
  • [2023-11-08 21:20:07]
  • 提交

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=1e5+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;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 10460kb

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: 10460kb

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: 2ms
memory: 10504kb

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: 4ms
memory: 10424kb

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: 4ms
memory: 10484kb

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: 0
Accepted
time: 5ms
memory: 11000kb

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:

Yes
4999 4998 4997 4996 4995 4994 4993 4992 4991 4990 4989 4988 4987 4986 4985 4984 4983 4982 4981 4980 4979 4978 4977 4976 4975 4974 4973 4972 4971 4970 4969 4968 4967 4966 4965 4964 4963 4962 4961 4960 4959 4958 4957 4956 4955 4954 4953 4952 4951 4950 4949 4948 4947 4946 4945 4944 4943 4942 4941 4...

result:

ok OK. (1 test case)

Test #7:

score: -100
Wrong Answer
time: 23ms
memory: 16400kb

input:

1
5000 200
2 121 161
35 27 5 1 189 173 2 37 107 140 172 108 53 163 19 127 102 174 71 178 42 72 74 167 118 120 175 28 75 128 106 190 112 86 171 13
109 110 109 183 17 77 159 188 157 56 14 104 55 179 121 171 64 123 196 140 38 29 134 130 163 108 187 42 68 26 156 138 80 143 182 4 174 67 63 76 79 69 142 3...

output:

Yes
4995 4991 4990 4989 4988 4987 4986 4985 4984 4983 4982 4981 4980 4979 4978 4977 4976 4975 4974 4973 4972 4971 4970 4969 4968 4967 4966 4965 4964 4963 4962 4961 4960 4959 4958 4957 4956 4955 4954 4953 4952 4951 4950 4949 4948 4947 4946 4945 4944 4943 4942 4941 4940 4939 4938 4937 4936 4935 4934 4...

result:

wrong answer two transactions are not equivalent. (test case 1)