QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276506 | #7738. Equivalent Rewriting | doyo# | RE | 16ms | 76356kb | C++14 | 2.0kb | 2023-12-05 22:08:42 | 2023-12-05 22:08:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
stack<int>s[100010];
int n,m,cnt;
struct Edge
{
int next;int to;
}edge[maxn];
int ru[maxn],tops[maxn],head[maxn];
void init(){
for(int i=1;i<=n;++i)
while(!s[i].empty())s[i].pop();
for(int i=1;i<=m;i++) head[i]=0,ru[i]=0;
cnt=0;
}
void addedge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
queue<int> q;
struct node
{
int id;int tops;
}a[maxn];
void topsort()
{
for(int i=1;i<=m;i++)
if(ru[i]==0) q.push(i),tops[i]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(tops[v]) continue;
ru[v]--;
if(!ru[v]) q.push(v),tops[v]=tops[u]+1;
}
}
}
bool cmp(node x,node y)
{
if(x.tops==y.tops) return x.id>y.id;
return x.tops<y.tops;
}
int main()
{
cin.tie(0);
cin.sync_with_stdio(0);
int T;cin>>T;
while(T--){
cin>>m>>n;
for(int i=1;i<=m;++i){
int p;cin>>p;
for(int j=1;j<=p;++j){
int t;cin>>t;
s[t].push(i);
}
}
for(int i=1;i<=n;++i){
if(!s[i].empty()){
int u=s[i].top();
s[i].pop();
while(!s[i].empty()){
addedge(s[i].top(),u);
ru[u]++;
s[i].pop();
}
}
}
topsort();
for(int i=1;i<=m;i++)
{
a[i].id=i;a[i].tops=tops[i];
}
sort(a+1,a+m+1,cmp);
bool ansflag=false;
for(int i=1;i<m;i++)
if(a[i+1].tops==a[i].tops) ansflag=true;
if(ansflag)
{
cout<<"Yes\n";
for(int i=1;i<=m;i++) cout<<a[i].id<<((i==m)?'\n':' ');
}
else cout<<"No\n";
init();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 75320kb
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: 11ms
memory: 76356kb
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: 11ms
memory: 74292kb
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: 7ms
memory: 75608kb
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: 75924kb
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: 16ms
memory: 74376kb
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
Runtime Error
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...