QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#692244#3846. Link-Cut Treetelgs#WA 3ms32332kbC++171.4kb2024-10-31 14:10:272024-10-31 14:10:30

Judging History

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

  • [2024-10-31 14:10:30]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:32332kb
  • [2024-10-31 14:10:27]
  • 提交

answer

// #pragma GCC optimize(2)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
using ll=long long;
using pii=pair<ll,ll>;
using ld=long double;

constexpr ll N=1e6+10,mod=1e8-3,INF=1e18;
constexpr ld inf=1e18,eps=1e-5;

ll n,m;
ll p[N],d[N];
bool st[N];
vector<ll> g[N];
map<pii,int> mp;
struct Node{
	ll u,v;
}tr[N];

ll find(ll x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}

void topsort(){
	queue<ll> q;
	for(int i=1;i<=n;i++){
		if(d[i]==1){
			q.push(i);
		}
	}

	while(!q.empty()){
		ll u=q.front();
		q.pop();

		for(auto v:g[u]){
			--d[v];
			// cout<<mp[{min(u,v),max(u,v)}]<<'\n';
			st[mp[{min(u,v),max(u,v)}]]=0;
			if(d[v]==1){
				q.push(v);
			}
		}
	}
}

void solve(){
	cin>>n>>m;
	
	mp.clear();
	for(int i=1;i<=n;i++){
		p[i]=i,d[i]=0;
		g[i].clear();
	}
	for(int i=1;i<=m;i++) st[i]=0;
	
	for(int i=1;i<=m;i++){
		cin>>tr[i].u>>tr[i].v;
		mp[{min(tr[i].u,tr[i].v),max(tr[i].u,tr[i].v)}]=i;
	}

	for(int i=1;i<=m;i++){
		ll u=tr[i].u,v=tr[i].v;

		d[u]++,d[v]++;
		g[u].push_back(v),g[v].push_back(u);
		st[i]=1;

		if(find(u)==find(v)){
			topsort();
			for(int j=1;j<=m;j++){
				if(st[j]) cout<<j<<' ';
			}
			cout<<'\n';
			return;
		}else{	
			p[find(u)]=find(v);
		}
	}

	cout<<"-1\n";
}

int main(){
    IOS;
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 32332kb

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:

wrong answer 1st lines differ - expected: '2 4 5 6', found: '2 4 5 6 '