QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731106#3846. Link-Cut Treezhuqiancheng1WA 327ms6776kbC++141.6kb2024-11-09 23:55:302024-11-09 23:55:31

Judging History

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

  • [2024-11-09 23:55:31]
  • 评测
  • 测评结果:WA
  • 用时:327ms
  • 内存:6776kb
  • [2024-11-09 23:55:30]
  • 提交

answer

#include <iostream>
#include <vector>
using namespace std;

long long T,n,m,a,b;
struct edge{
    int id,u1,u2;
};

int f[100002];

int get(int x){
    if(x==f[x])return x;
    return f[x]=get(f[x]);
}
void unite(int x,int y){
    if(get(x)!=get(y)){
        f[get(x)]=get(y);
    }
}
bool isSameSet(int x, int y) {
    return get(x) == get(y);
}

int main()
{
    cin>>T;
    while(T>0){
        for(int i=0;i<100001;i++)f[i]=i;
        vector<edge> vec;
        edge e0;
        e0.id=0;
        e0.u1=0;
        e0.u2=0;
        int *ver;
        bool bo=1,Bo=1;
        T--;
        cin>>n>>m;
        ver=new int[n+2]{0};
        for(int i=0;i<m;i++){
            cin>>a>>b;
            if(bo==0)continue;
            if(isSameSet(a,b)){
                bo=0;}
            else {unite(a,b);}
            edge e;
            e.id=i;
            e.u1=a;
            e.u2=b;
            vec.push_back(e);
            ver[a]++;
            ver[b]++;
            if(i==m-1){
                cout<<-1<<endl;
                Bo=0;
            }

        }
        if(Bo==0){
            delete ver;
            continue;}
        for(int i=vec.size()-1;i>=0;i=i-1){
            if(ver[vec[i].u1]==1||ver[vec[i].u2]==1){
                ver[vec[i].u1]--;
                ver[vec[i].u2]--;
                vec[i]=e0;
            }
        }
        for(int i=0;i<vec.size();i++){
            if(vec[i].id!=0){
                cout<<vec[i].id+1;
                if(i!=vec.size()-1)cout<<' ';}
        }
        cout<<endl;
        delete ver;
    }
    return 0;
}

詳細信息

Test #1:

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

input:

2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3

output:

2 4 5 6
-1

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 327ms
memory: 6776kb

input:

1658
9 20
6 4
5 8
1 7
2 3
3 8
3 1
4 8
5 3
7 6
1 6
4 9
4 1
9 3
2 5
4 5
8 9
1 8
4 2
5 7
3 6
14 78
13 12
10 8
2 10
6 13
2 14
13 1
14 10
9 6
2 13
8 3
9 8
5 6
14 12
8 1
9 14
9 5
12 6
5 10
3 12
10 4
8 5
9 10
6 8
1 6
12 4
3 13
1 5
10 3
13 9
10 13
2 5
4 7
7 1
7 6
9 3
2 12
1 10
9 1
1 14
3 1
3 4
11 1
11 6
7 1...

output:

2 5 6 7 8
3 5 7
-1
-1
2 3 4 7 9 12 13
3 4 5 6 9
3 4 5 7 11 12
2 3
8 9 10 11
2 3 5 7 10 11 12 13 14 15 16
2 3 5
-1
3 4
-1
-1
6 8 10 11 13 14 15
5 6
5 7
2 3 4
-1
3 6
-1
2 3 5
-1
-1
6 8 9 10 11 12 14 15 16
2 6
-1
-1
-1
7 8 12 13 15 17 18
-1
4 5 8 10 12
3 4 5 6 9 10
4 6 8
2 3 4
2 3 5 6
2 5 6 7 8 10 13 1...

result:

wrong answer 1st lines differ - expected: '2 5 8', found: '2 5 6 7 8'