QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#247565 | #7738. Equivalent Rewriting | Redcrown# | WA | 2ms | 20268kb | C++17 | 1.9kb | 2023-11-11 14:56:48 | 2023-11-11 14:56:49 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=3e5+5;
int n,m;
inline int red(){
int data=0;bool w=0;char ch=getchar();
while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
if(ch=='-') w=1,ch=getchar();
while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
return w?-data:data;
}
vector <int> op[N];
vector <int> G[N];
int du[N],num,pos;
void add(int a,int b){
G[a].push_back(b);
++du[b];
}
int ans[N],top;
void solve(){
n=red();m=red();
top=0;
for(int i=1;i<=max(n,m);i++){
op[i].clear();du[i]=0;G[i].clear();
}
for(int i=1;i<=n;i++){
scanf("%d",&num);
for(int j=1;j<=num;j++){
scanf("%d",&pos);
op[pos].push_back(i);
}
}
for(int i=1;i<=m;i++){
int last=-1;
for(auto v:op[i]){
if(last==-1){
last=v;
}else{
add(last,v);
last=v;
}
}
}
queue <int> Q;
for(int i=1;i<=n;i++){
if(!du[i]){
Q.push(i);
}
}
int flag=0;
while(!Q.empty()){
if(!flag&&Q.size()>=2){
int a=Q.front();Q.pop();
int b=Q.front();Q.pop();
if(a<b)swap(a,b);
ans[++top]=a;
for(auto v:G[a]){
--du[v];
if(!du[v]){
Q.push(v);
}
}
ans[++top]=b;
for(auto v:G[b]){
--du[v];
if(!du[v]){
Q.push(v);
}
}
flag=1;
continue;
}
int a=Q.front();Q.pop();
ans[++top]=a;
for(auto v:G[a]){
--du[v];
if(!du[v]){
Q.push(v);
}
}
}
if(!flag){
printf("No\n");
}else{
printf("Yes\n");
for(int i=1;i<=n;i++){
printf("%d%c",ans[i]," \n"[i==n]);
}
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int T=1;
T=red();
while(T--)solve();
return 0;
}
/*
4
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
3 2
2 1 2
1 1
1 2
4 4
2 1 2
2 2 3
2 3 4
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 18252kb
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: -100
Wrong Answer
time: 2ms
memory: 20268kb
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:
No
result:
wrong answer jury found an answer but participant did not (test case 1)