QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658166#7738. Equivalent RewritingDetach#WA 7ms55000kbC++202.4kb2024-10-19 16:17:362024-10-19 16:17:37

Judging History

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

  • [2024-10-19 16:17:37]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:55000kb
  • [2024-10-19 16:17:36]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <algorithm>
// #include <queue>
// #include <map>
// #include <iostream>
// #include <string>
// #include <set>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back

using namespace std;    
using namespace __gnu_pbds;

using LL = long long; 
using PII = pair<int, int>;
using i128 = __int128_t;
using ULL = unsigned long long;
using Tree = tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int INF = 0x3f3f3f3f, MOD = 1e9 + 7, N = 1e6 + 5, M = 1e6 + 5;
constexpr LL LINF = 0x3f3f3f3f3f3f3f3f;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
int x,y;
vector<int> v[N];
set<int> g[N];
int mx[N];
int d[N];
void solve(){
    cin>>n>>m;
    rep(i,1,n){
        int x;
        cin>>x;
        rep(_,1,x){
            cin>>y;
            mx[y]=i;
            v[i].pb(y);
        }
    }

    // rep(i,1,m){
    //     cout<<i<<" "<<mx[i]<<endl;
    // }
    
    rep(i,1,n){
        for(int x : v[i]){
            if(mx[x]==i) continue;
            if(g[i].count(mx[x])) continue;
            g[i].insert(mx[x]);
            // cout<<i<<" "<<x<<" "<<mx[x]<<endl;
            d[mx[x]]++;
        }
    }

    // rep(i,1,n){
    //     cout<<i<<": ";
    //     for(int x : g[i]){
    //         cout<<x<<" ";
    //     }
    //     cout<<endl;
    // }
    
    priority_queue<int> q;
    vector<int> ans;
    rep(i,1,n) if(d[i]==0) q.emplace(i);
    while(!q.empty()){
        int u=q.top();q.pop();
        
        ans.pb(u);
        for(int v : g[u]){
            if(--d[v]==0) q.emplace(v);
        }
    }
    int idx=1;
    for(int x : ans){
        if(x==idx++){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
    rep(i,0,n-1){
        cout<<ans[i];
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;

    rep(i,1,n) v[i].clear(),g[i].clear();
    rep(i,1,n) d[i]=0;
}

signed main()
{
    // (.*)   "$1"
    // freopen("park.in", "r", stdin);
    // freopen("park.out", "w", stdout);
	// cout << fixed << setprecision(2);
    // srand(NULL);
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
	cin >> T;

    while(T -- )
        solve();

    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 55000kb

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: 5ms
memory: 54760kb

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)