QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#679768#3846. Link-Cut TreelhwWA 181ms15036kbC++142.0kb2024-10-26 18:28:392024-10-26 18:28:39

Judging History

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

  • [2024-10-26 18:28:39]
  • 评测
  • 测评结果:WA
  • 用时:181ms
  • 内存:15036kb
  • [2024-10-26 18:28:39]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<array>
#include<random>
#include<string>
#include<time.h>
#include<cstring>
#include<set>
#include<cmath>
#include<queue>
#define int long long
#define endl '\n'
#define F first
#define S second
#define sz size()
#define ln cout<<'\n'
#define B begin()
#define pb push_back
#define D end()
#define pii pair<int,int> 

using namespace std;
const int N=1e5+10;
const int mod=1e9;  
int n,m;
int f[N];

struct Nod{
	int u;
	int v;
	int w;
}g[N];

bool cmp(Nod a,Nod b)
{
	return a.w<b.w;
}

int find1(int u)
{
	if(u!=f[u])f[u]=find1(f[u]);
	return f[u];
}

struct NN{
	int u;
	int v;
	int c;
};
vector<NN> ss;
bool vis[N];
vector<int> ans;
bool ok=0;
void dfs(int u,int pa,vector<vector<pair<int,int>>>&mp)
{
	if(ok)return;
	vis[u]=1;
	for(auto t:mp[u])
	{
		int v=t.first;
		if(v==pa)continue;
		ss.push_back({u,v,t.second});
		if(vis[v]==1)
		{
			while(ss[ss.size()-1].u!=v)
			{
				ans.push_back(ss[ss.size()-1].c);
				ss.pop_back();
			}
			ans.push_back(ss[ss.size()-1].c);
			ok=1;
			return;
		}
		dfs(v,u,mp);
		if(ok)return;
	}
	ss.pop_back();
}

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		vis[i]=0;
		
		
	}
	ans.clear();ss.clear();
	ok=0;
	vector<vector<pair<int,int>>> mp(n+1);
	for(int i=1;i<=n;i++)f[i]=i;

	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[i]={u,v,i};
	}
	sort(g,g+m,cmp);
	for(int i=0;i<m;i++)
	{
		int u=g[i].u;
		int v=g[i].v;
		int fa=find1(u);
		int fb=find1(v);
		mp[u].push_back({v,i});
		mp[v].push_back({u,i});
		if(fa==fb)
		{
			dfs(g[0].u,-1,mp);
			sort(ans.begin(),ans.end());
			cout<<ans[0]+1;
			
			for(int i=1;i<ans.size();i++)
			{
				cout<<' '<<ans[i]+1;
			}
			
			cout<<endl;
			return;
		}
		if(fa!=fb)f[find1(u)]=f[find1(v)];
	}
	cout<<-1<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc=1;
	cin>>tc;
	while(tc--)
	{
		solve();
	}
	//cout<<"dafc";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5620kb

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
Wrong Answer
time: 181ms
memory: 15036kb

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
2
1 3 4
2 3 4
2
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
1
1
1 2 3 4
3 5 6
3
4 6 8
-1
1 2 3 5 6
1 3 4
1 3 5 8
1 2 4 6 7 8 11 12 13
1 4...

result:

wrong answer 2nd lines differ - expected: '3 5 7', found: '2'