QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#244130 | #7738. Equivalent Rewriting | TJUHuangTao | WA | 26ms | 90156kb | C++20 | 1.6kb | 2023-11-08 21:26:25 | 2023-11-08 21:26:25 |
Judging History
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=1e6+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: 78248kb
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: 4ms
memory: 79600kb
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: 7ms
memory: 78196kb
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: 15ms
memory: 78784kb
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: 7ms
memory: 78452kb
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: 6ms
memory: 78544kb
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: 26ms
memory: 90156kb
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)