MLE + TLE 60pts悬关
查看原帖
MLE + TLE 60pts悬关
1050431
DevilsFlame楼主2024/8/13 09:14
#include<bits/stdc++.h>
#define N 1000010
#define M 1e9
using namespace std;
vector <int> e[N];
map <int,map<int,bool> > pl;
struct Node
{
	int a,b,w;
}gg;
vector <Node> l;
int n,m,k,a,b,ans = M,s[N],ll,f[N];
bool vis[N];
queue <int> q;
inline void min_s()
{
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(int i = 0;i < e[x].size();i ++)
		{
			int v = e[x][i];
			if(vis[v]) continue;
			vis[v] = 1;
			s[v] = s[x] + 1;
			q.push(v);
		}
	}
	return;
}
inline void read(int &x)
{
	x = 0;
	int f = 1;
	char s = getchar();
	while(s < '0' || s > '9')
	{
		if(s == '-') f = -1;
		s = getchar();
	}
	while(s >= '0' && s <= '9')
	{
		x = x * 10 + s - 48;
		s = getchar();
	}
	x *= f;
	return;
}
bool cmp(Node x,Node y)
{
	return x.w < y.w;
}
inline int find(int x)
{
	return (f[x] == x ? x : f[x] = find(f[x]));
}
int main()
{
	read(n),read(m),read(k);
	if(m < n)
	{
		puts("Poor D!");
		return 0;
	}
	for(int i = 1;i <= m;i ++)
	{
		read(a),read(b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i = 1;i <= k;i ++)
	{
		read(a);
		s[a] = 0;
		q.push(a);
		vis[a] = 1;
	}
	min_s();
	for(int i = 1;i <= n;i ++)
	{
		f[i] = i;
		while(e[i].size())
		{
			int v = e[i][0];
			e[i].erase(e[i].begin());
			if(pl[i][v]) continue;
			gg.a = i,gg.b = v;
			gg.w = max(s[i],s[v]);
			l.push_back(gg);
			pl[v][i] = 1;
		}
	}
	sort(l.begin(),l.end(),cmp);
	for(int i = 0;i < m;i ++)
	{
		a = find(l[i].a),b = find(l[i].b);
		if(a == b)
		{
			cout << l[i].w << endl;
			return 0;
		}
		else f[a] = b;
	}
	puts("Poor D!");
	return 0;
}
2024/8/13 09:14
加载中...