QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246528 | #7738. Equivalent Rewriting | trigriffin | WA | 1ms | 6304kb | C++14 | 1.8kb | 2023-11-10 21:43:50 | 2023-11-10 21:43:50 |
Judging History
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)