QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #604901 | #3846. Link-Cut Tree | Sunlight9# | TL | 0ms | 36320kb | C++20 | 2.1kb | 2024-10-02 14:28:45 | 2024-10-02 14:28:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M=5e6+5;
int fa[M],ans[M];
int t,n,m;
struct node{
int u,v;
}a[M];
int nxt[M],to[M],head[M],adj[M],tot;
void add(int u,int v,int w){
nxt[++tot]=head[u];
head[u]=tot;
to[tot]=v;
adj[tot]=w;
return ;
}
int findr(int x){
if (fa[x]==x) return x;
return fa[x]=findr(fa[x]);
}
void merge(int u,int v){
int fu=findr(u),fv=findr(v);
if (fu!=fv) fa[fu]=fv;
return ;
}
queue<int> q;
int pre[M];
bool vis[M];
void bfs(int s,int e){
for (int i=1;i<=n;i++) vis[i]=0;
q.push(s);vis[s]=1;
while (!q.empty()){
int no=q.front();q.pop();
// cerr << no << "\n";
for (int i=head[no];i;i=nxt[i]){
int v=to[i];
// cerr << v << "\n";
if (vis[v]) continue;
pre[v]=adj[i];
q.push(v);vis[v]=1;
}
}
return ;
}
void work(int now){
tot=0;
memset(head, 0, sizeof(head));
for (int i=1;i<now;i++){
add(a[i].u,a[i].v,i);
add(a[i].v,a[i].u,i);
}
int s=a[now].u,e=a[now].v;
bfs(s,e);
// cerr << "ok\n";
int noww=e;
int len=0;
while (noww!=s){
ans[++len]=pre[noww];
int id=pre[noww];
if (a[id].u!=noww) noww=a[id].u;
else noww=a[id].v;
}
ans[++len]=now;
sort(ans+1,ans+len+1);
for (int i=1;i<len;i++) cout<<ans[i]<<" ";
cout<<ans[len]<<endl;
return ;
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n>>m;
for (int i=1;i<=n;i++) fa[i]=i;
int f=m+1;
for (int i=1;i<=m;i++){
cin>>a[i].u>>a[i].v;
if (findr(a[i].u)==findr(a[i].v)) {work(i);f=i;break;}
merge(a[i].u,a[i].v);
}
if (f==m+1) cout<<-1<<endl;
for (int j=f+1;j<=m;j++) {
int u,v;
cin>>u>>v;
}
}
return 0;
}
/*
3
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3
4 5
1 2
2 3
3 4
3 1
4 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 36320kb
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...
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 ...