QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210731 | #3846. Link-Cut Tree | beckham_of_laiwu | RE | 1ms | 8208kb | C++14 | 1.9kb | 2023-10-11 19:29:40 | 2023-10-11 19:29:41 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
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, tx, ty;
int fa[N],head[N],p[N],vis[N],pre[N],ans[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 || vis[t]) continue;
if(dfs(t,now,tar))
{
p[++ num] = edge[i].val;
return 1;
}
}
}
void bfs()
{
queue <int> q;
while(!q.empty()) q.pop();
q.push(x);
while(! q.empty())
{
int now = q.front();
q.pop();
for(int i = head[now];i;i = edge[i].nxt)
{
int t = edge[i].to;
if(t == pre[now]) continue;
pre[t] = now;
ans[t] = edge[i].val;
q.push(t);
}
}
}
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);
bfs();
tx = x;
ty = y;
flag = 1;
}
else
{
addedge(x,y,i);
addedge(y,x,i);
fa[getfa(x)] = getfa(y);
}
}
if(num)
{
int now = ty;
while(now != tx)
{
//printf("now = %d\n",now);
p[++ num] = ans[now];
now = pre[now];
}
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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8208kb
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
Runtime Error
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...