QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#587559 | #3846. Link-Cut Tree | SocialPanda | TL | 4ms | 18808kb | C++23 | 2.4kb | 2024-09-24 20:37:54 | 2024-09-24 20:37:54 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long
//#define LL long long
#define double long double
//#define lf Lf
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define PII pair<int,int>
#define Gheap priority_queue<int,vector<int>,greater<int>>
#define Lheap priority_queue<int>
#define MAXN 0x3f3f3f3f
#define MINN -0x3f3f3f3f
using namespace std;
//const int N=1e6+100,M=2*N;
//int e[N],w[M],h[M],ne[M],idx;
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
vector<int> vec;
unordered_map<int,int> st;
unordered_map<int,vector<PII>> edge;
int fg=0;
void dfs(int cur,int fa)
{
st[cur]=1;
for(auto z:edge[cur])
{
if(z.fi == fa) continue;
if(st[z.fi]==1 and fg==0)
{
fg=z.fi;
return;
}
if(fg==0)
{
dfs(z.fi,cur);
}
if(fg!=0)
if(fg!=cur)
{
vec.pb(z.se);
}
else if(fg==cur)
{
vec.pb(z.se);
fg=-1;
}
}
}
void solve()
{
int n,m;
cin>>n>>m;
DSU dsu(1000000);
edge.clear();
int point = -1;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(dsu.same(a,b))
{
edge[a].pb({b,i});
edge[b].pb({a,i});
point = a;
break;
}
edge[a].pb({b,i});
edge[b].pb({a,i});
dsu.merge(a,b);
}
if(point==-1) cout<<-1<<endl;
st.clear();
vec.clear();
dfs(point,-1);
sort(vec.begin(),vec.end());
for(auto z:vec)
{
cout<<z;
if(z!=*vec.rbegin()) cout<<' ';
}
cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt=1;
cin >> tt;
while(tt--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 18808kb
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...