QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#702745#7738. Equivalent Rewritinghellocccl#WA 1ms5724kbC++202.4kb2024-11-02 16:31:012024-11-02 16:31:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 16:31:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5724kb
  • [2024-11-02 16:31:01]
  • 提交

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)