QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#691803#3846. Link-Cut Treezzfs#AC ✓311ms17232kbC++142.5kb2024-10-31 13:03:172024-10-31 13:03:17

Judging History

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

  • [2024-10-31 13:03:17]
  • 评测
  • 测评结果:AC
  • 用时:311ms
  • 内存:17232kb
  • [2024-10-31 13:03:17]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxN = 2e5 + 7;

int T, n, m, head[maxN], cnt, fa[maxN], st, vis[maxN], cnt2, d[maxN], ans[maxN];

struct Edge {
    int from, to, dis;
}e[maxN << 1], e2[maxN << 1];

struct Now {
    int val, point;
}now[maxN];

inline void add(int u, int v, int w)
{
    e[++cnt].from  = u; e[cnt].to = v;
    e[cnt].dis = w;
}

inline void add2(int u, int v, int w)
{
    e2[++cnt2].from = head[u]; e2[cnt2].to = v;
    e2[cnt2].dis = w; head[u] = cnt2;
}


bool cmp(Edge x, Edge y)
{
    return x.dis < y.dis;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void bfs()
{
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        if(d[i] == 1)
            q.push(i);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = e2[i].from) {
            int y = e2[i].to;
            d[y]--;
            ans[e2[i].dis] = 1;
            if(d[y] == 1)
                q.push(y);
        }
    }
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(head, 0, sizeof head); memset(vis, 0, sizeof vis); memset(ans, 0, sizeof ans); memset(d, 0, sizeof d);
        cnt = cnt2 = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            add(x, y, i);
        }
        for(int i = 1; i <= n; ++i)
            fa[i] = i;
        sort(e + 1, e + 1 + m, cmp);
        bool succ = false;
        for(int i = 1; i <= m; ++i) {
            int x = e[i].from, y = e[i].to;
            int fx = find(x), fy = find(y);
            if(fx == fy) {
                st = i;
                for(int j = 1; j <= i; ++j) {
                    add2(e[j].from, e[j].to, e[j].dis);
                    add2(e[j].to, e[j].from, e[j].dis);
                    d[e[j].from]++; d[e[j].to]++;
                }
                bfs();
                succ = true;
                break;
            }
            fa[fx] = fy;
        }
        if(succ) {
            int i = 1;
            for(; i <= st; ++i)
                if(ans[i] == 0) {
                    printf("%d", i++);
                    break;
                }
            for(;i <= st; ++i)
                if(ans[i] == 0)
                    printf(" %d", i);
            printf("\n");
        }
        else
            printf("-1\n");
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 12752kb

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: 0
Accepted
time: 311ms
memory: 17232kb

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 8
3 5 7
1 3 4
2 3 4
2 3 4 7 13
1 3 4 5 9
3 4 7 12
1 2 3
8 10 11
2 3 5 7 12 13 14 15 16
1 2 3 5
1 2 4
1 3 4
1 2 3
1 2 3
10 11 15
1 5 6
1 5 7
1 2 3 4
-1
1 3 6
-1
1 2 3 5
-1
-1
6 8 9 10 11 16
1 2 6
2 3 4
-1
-1
7 8 12 13 18
-1
1 4 8 12
3 5 10
4 6 8
1 2 3 4
3 5 6
5 8 10 15
4 6 8
-1
1 2 3 5 6
1 3 4
1 ...

result:

ok 1658 lines

Test #3:

score: 0
Accepted
time: 152ms
memory: 15556kb

input:

10
100000 100000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 10 lines