QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#702745 | #7738. Equivalent Rewriting | hellocccl# | WA | 1ms | 5724kb | C++20 | 2.4kb | 2024-11-02 16:31:01 | 2024-11-02 16:31:02 |
Judging History
answer
//ALL IN
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int long long
#define double long double
const int N=2e5+7;
const int mod=1e9+7;
const int inf=4e18;
mt19937 rnd(time(0));
clock_t start,over;// start=clock(); last=(final-over)*1.0/1000
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar();}return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;}
int a[N];
vector<int>ans;
vector<int>g[N];
int dout[N];
void dfs(int x){
// cout<<"x :"<<x<<'\n';
ans.push_back(x);
for(auto y:g[x]){
dfs(y);
}
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
a[i]=0;
dout[i]=0;
}
ans.clear();
for(int i=1;i<=n;i++){
int x;cin>>x;
for(int j=1;j<=x;j++){
int y;cin>>y;
if(a[y]!=0){
g[a[y]].push_back(i);
a[y]=i;
}else{
a[y]=i;
}
}
}
if(n==1){
cout<<"No"<<'\n';
return;
}
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end());
g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end());
}
for(int i=1;i<=n;i++){
for(auto y:g[i]){
dout[y]++;
}
}
queue<int>q;
for(int i=n;i>=1;i--){
if(dout[i]==0){
// cout<<i<<'\n';
// dfs(i);
q.push(i);
}
}
while(q.size()){
int x=q.front();
// cout<<x<<'\n';
q.pop();
ans.push_back(x);
for(auto y:g[x]){
dout[y]--;
if(dout[y]==0){
q.push(y);
}
}
}
int flag=1;
for(int i=0;i<ans.size();i++){
if(ans[i]!=i+1){
flag=0;
break;
}
}
if(flag){
cout<<"No"<<'\n';
}else{
cout<<"Yes"<<'\n';
for(auto i:ans){
cout<<i<<" ";
}
cout<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
while(_--)solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
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: 1ms
memory: 5668kb
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)