QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561831 | #3846. Link-Cut Tree | AmiyaCast# | AC ✓ | 60ms | 8312kb | C++14 | 1.9kb | 2024-09-13 11:17:40 | 2024-09-13 11:17:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
const ll inf = 1145141919810;
using namespace std;
inline ll read() {
ll x=0,f=1;
char c=getchar();
while (c<'0' || c>'9') {
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline void print(ll x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
return ;
}
inline void pprint(ll x) {
print(x);
puts("");
}
int n, m;
vector<vector<pair<int,int> > > g;
const int N = 1e5 + 7;
int fa[N];
ll dis[N];
int get(int x) {
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
const int M = 1e5 + 7;
int nxt[M << 1], to[M << 1], head[N], w[M << 1], cnt = 1;
void add(int x, int y, ll z){
nxt[++cnt] = head[x];
to[cnt] = y;
w[cnt] = z;
head[x] = cnt;
}
void slv() {
n = read(), m = read(); cnt = 1;
rep(i, 0, n) fa[i] = i, head[i] = 0;
vector<int> ans;
int f = 0;
int st = 0, ed = 0;
rep(i, 1, m) {
int x = read(), y = read();
if(f) continue;
int fx = get(x), fy = get(y);
if(fx == fy) {
st = x, ed = y;
f = 1;
ans.pb(i);
continue;
}
fa[fx] = fy;
add(x, y, i);
add(y, x, i);
}
if(!f) {
puts("-1");
return ;
}
vector<int> pre(n + 1);
queue<int> q;
q.push(st);
while(q.size()){
int x = q.front();
q.pop();
for(int i = head[x]; i; i = nxt[i]){
if(!pre[to[i]] && to[i] != st){
q.push(to[i]);
pre[to[i]] = (i ^ 1);
}
}
}
for(int i = ed; i != st; i = to[pre[i]]){
ans.pb(w[pre[i]]);
}
sort(ans.begin(), ans.end());
rep(i, 0, (int)ans.size() - 1){
printf("%d%c", ans[i], i == (int)ans.size() - 1 ? '\n' : ' ');
}
}
int main() {
int T = read();
while(T--) {
slv();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5804kb
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: 27ms
memory: 8312kb
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: 60ms
memory: 8004kb
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