QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246480#7738. Equivalent RewritingLZX_OVO#WA 2ms11836kbC++142.7kb2023-11-10 20:55:302023-11-10 20:55:32

Judging History

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

  • [2023-11-10 20:55:32]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11836kb
  • [2023-11-10 20:55:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int nums[2000005];
struct EDGE{
    int to, nt;
}edge[4000005];
int head[2000005];
int in[2000005];
int out[2000005];
int cnt = 0;


void add_edge(int u , int v ){
    edge[++cnt] = {v , head[u]};
    head[u] = cnt;
}

set<pair<int ,int> >st;

int anspos= 0;
int ansval =0;

int n , m , opnum , tmppos;

bool dfs(int id){
    if(id == m+1){
        return false;
    }
    int nextid = id+1;
    int ret = false;
    for(int i = head[id] ; i ; i=edge[i].nt){
        int v = edge[i].to;
        if(--in[v] == 0){
            if(nextid == v){
                continue;
            }else{
                anspos = nextid;
                ansval = v;
                ret = 1;
                break;
            }
        }
    }
    if(ret){
        return true;
    }else{
        return dfs(nextid);
    }
}

void solve(){
    anspos= 0;
    ansval =0;
    st.clear();
    cnt = 0;
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        head[i] = 0;
    }
    for(int i = 1;i<=m;i++){
        nums[i] = 0;
    }
    for(int i = 1;i<=n;i++){
        cin >> opnum;
        for(int j = 1;j<=opnum;j++){
            cin >> tmppos;
            if(nums[tmppos] == 0){
                nums[tmppos] = i;
            }else{
                int be = nums[tmppos];
                int af = i;
                if(st.find(make_pair(be , af)) == st.end()) {
                    add_edge(be , af);
                    st.insert(make_pair(be , af));
                    //cout << "add_edge" << be <<" " << af << endl;
                    in[af]++;
                    out[be]++;
                }
                nums[tmppos] = af;
            }
        }
    }
    //拓扑
    int errid = 0;
    for(int i = 1;i<=n;i++){
        if(in[i] == 0){
            if(i != 1){
                errid = i;
                break;
            }
        }
    }
    if(errid != 0){
        cout << "Yes" <<'\n';
        cout << errid ;
        for(int i = 1;i<=n;i++){
            if(i == errid)continue;
            cout<< " " << i ;
        }
        cout << "\n";
        return;
    }
    
    if(dfs(1) == true){
        cout << "Yes" <<'\n';
        cout << "1";
        for(int i = 2;i<=n;i++){
            if(i == ansval ){
                continue;
            }
            if(i == anspos){
                cout << " " << ansval ;
            }
            cout <<" "  << i ;
        }
        cout << "\n";
    }else{
        cout << "No" << '\n';
    }
}




int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 11832kb

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

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)