QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731106 | #3846. Link-Cut Tree | zhuqiancheng1 | WA | 327ms | 6776kb | C++14 | 1.6kb | 2024-11-09 23:55:30 | 2024-11-09 23:55:31 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'