QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#210733 | #3846. Link-Cut Tree | beckham_of_laiwu | TL | 1ms | 5960kb | C++14 | 1.4kb | 2023-10-11 19:32:41 | 2023-10-11 19:32:42 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
struct qwq{
int nxt,to,val;
};
qwq edge[N * 2];
int n,m,T,num,x,y,cnt;
int fa[N],head[N],p[N],vis[N];
void addedge(int f,int t,int v)
{
edge[++ cnt].nxt = head[f];
edge[cnt].to = t;
edge[cnt].val = v;
head[f] = cnt;
}
int getfa(int x)
{
if(fa[x] != x) fa[x] = getfa(fa[x]);
return fa[x];
}
int dfs(int now,int f,int tar)
{
//printf("now = %d\n",now);
//if(vis[now]) return 0;
//vis[now] = 1;
if(now == tar)
{
return 1;
}
for(int i = head[now];i;i = edge[i].nxt)
{
int t = edge[i].to;
if(t == f) continue;// || vis[t]) continue;
if(dfs(t,now,tar))
{
p[++ num] = edge[i].val;
return 1;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
scanf("%d%d",&n,&m);
int flag = 0;
num = 0; cnt = 0;
for(int i = 1;i <= n;i ++)
fa[i] = i;
memset(head,0,sizeof(int) * n);
for(int i = 1;i <= m;i ++)
{
scanf("%d%d",&x,&y);
if(flag) continue;
if(getfa(x) == getfa(y))
{
p[++ num] = i;
dfs(x,0,y);
flag = 1;
}
else
{
addedge(x,y,i);
addedge(y,x,i);
fa[getfa(x)] = getfa(y);
}
}
if(num)
{
sort(p + 1,p + num + 1);
for(int i = 1;i < num;i ++)
printf("%d ",p[i]);
printf("%d\n",p[num]);
}
else printf("-1\n");
}
return (0 ^ 0);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5960kb
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
Time Limit Exceeded
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...