QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#587559#3846. Link-Cut TreeSocialPandaTL 4ms18808kbC++232.4kb2024-09-24 20:37:542024-09-24 20:37:54

Judging History

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

  • [2024-09-24 20:37:54]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:18808kb
  • [2024-09-24 20:37:54]
  • 提交

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...

output:


result: