QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343819#7738. Equivalent Rewritingucup-team992#WA 1ms3496kbC++201.8kb2024-03-03 05:37:082024-03-03 05:37:08

Judging History

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

  • [2024-03-03 05:37:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2024-03-03 05:37:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
typedef int uci;
#define int long long
#define ll long long
#define ar array

void solve(){
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n);
    vector<set<int>> adj(n);
    vector<vector<int>> vals(m);
    for(int i{}; i < n; ++i){
        int p;
        cin >> p;
        for(int j{}; j < p; ++j){
            int t;
            cin >> t;
            t--;
            vals[t].push_back(i);
        }
    }

    vector<int> deg(n);
    for(int i{}; i < m; ++i){
        if(vals[i].size() > 1){
            for(int j{}; j < vals[i].size()-1; ++j){
                if(!adj[vals[i].back()].count(vals[i][j])){
                    deg[vals[i][j]]++;
                    adj[vals[i].back()].insert(vals[i][j]);
                }
            }
        }
    }

    priority_queue<int, vector<int>, greater<>> pq;
    vector<int> out;
    vector<bool> taken(n);
    for(int i{}; i < n; ++i){
        if(deg[i] == 0){
            pq.push(i);
            taken[i] = true;
        }
    }

    while(pq.size()){
        int v = pq.top();
        pq.pop();
        out.push_back(v);
        for(int j : adj[v]){
            deg[j]--;
            if(!taken[j] && deg[j] == 0){
                pq.push(j);
            }
        }
    }

    reverse(out.begin(), out.end());
    if(out.size() == n){
        for(int i{}; i < n; ++i){
            if(out[i] != i){
                cout << "YES\n";
                for(int j : out)
                    cout << j+1 << ' ';
                cout << '\n';
                return;
            }
        }
    }
    cout << "NO\n";
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for(int i{}; i<t; ++i)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3496kb

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:

wrong answer Token parameter [name=yesno] equals to "YES", doesn't correspond to pattern "Yes|No" (test case 1)