QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246527#7738. Equivalent RewritingLZX_OVO#WA 2ms13696kbC++142.4kb2023-11-10 21:43:282023-11-10 21:43:29

Judging History

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

  • [2023-11-10 21:43:29]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13696kb
  • [2023-11-10 21:43:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 2000005
struct EDGE{
    int to , nt;
}edge[N*2];
int cnt;
int head[N];
int k[N];
int in[N];
int out[N];
void add_edge(int u , int v){
    edge[++cnt] = {v , head[u]};
    head[u] = cnt;
};
set<pair<int,int> >st;
int ans[N];
int anscnt = 1;
int n , m , frontk_cnt , numtmp;

void dfs(int id){
    vector<int>add_ans;
    for(int i = head[id];i; i = edge[i].nt){
        int v = edge[i].to;
        if((--in[v]) == 0 ){
            add_ans.push_back(v);
        }
        
    }
    sort(add_ans.begin() , add_ans.end()) ;
    reverse(add_ans.begin() , add_ans.end());
    for(auto x : add_ans){
        ans[++anscnt ] = x;
    }
    for(auto x : add_ans){
        dfs(x);
    }

}

void solve(){
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        in[i] = 0;
        out[i] = 0;
        head[i] = 0;
    }
    for(int i = 1;i<=m;i++){
        k[i] = 0;
    }
    st.clear();
    cnt = 0;


    for(int i = 1;i<=n;i++){
        cin >> frontk_cnt;
        for(int j = 1;j<=frontk_cnt;j++){
            cin >> numtmp;   
            if(k[numtmp] == 0) {
                k[numtmp] = i;
            }else{
                if(st.find(make_pair(k[numtmp] , i)) == st.end()){
                    add_edge(k[numtmp] , i);
                    st.insert(make_pair(k[numtmp] , i));
                    out[k[numtmp]] ++;
                    in[i] ++ ;
                }
                k[numtmp] = i;
            }
        }
    }
    //是否有唯一起点
    for(int i = 1;i<=n;i++){
        if((in[i] == 0) && (i != 1)){
            //输出
            cout << "Yes" << "\n"; 
            cout << i  ;
            for(int j = 1;j<=n;j++){
                if(j!=i){
                    cout << " " << j;
                }
            }
            cout <<"\n";
            return;
        }
    }
    ans[1] = 1;
    dfs(1);
    bool flag = 0;
    for(int i = 1;i<=n;i++){
        if(ans[i] != i){
            flag = 1;
        }
    }
    if(flag == 1){
        cout << "Yes" << "\n";
        for(int i = 1; i<=n;i++){
            if(i == 1){
                cout << 1;
            }else{
                cout << " " << i ;
            }
        }
        cout << "\n";
    }else{
        cout << "No" << "\n";
    }
}

int main(){
    int t; cin >> t;
    while(t--){
        solve();   
    }
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13696kb

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: 13684kb

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)