제출 #95211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95211		hamzqq9	007 (CEOI14_007)	C++14	16 / 100	1097 ms	177712 KiB

007

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1ll<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 600005
#define M 1000003
#define LOG 16
#define KOK 650
#define EPS 0.00001
using namespace std;

int n,m,cur,cur0,s1,s2,x,y;
int dis[4][N],vis[N],vdag[2][N],dep[2][N],frb[N],nodes[2][N];
vector<int> v[N],dag[2][N];

void bfs(int start,int ar) {

	queue<ii> q;

	for(int i=1;i<=n;i++) vis[i]=0;

	q.push({start,0});

	while(!q.empty()) {

		ii cur=q.front();

		q.pop();

		if(vis[cur.st]) continue ;

		vis[cur.st]=1;

		dis[ar][cur.st]=cur.nd;

		for(int i:v[cur.st]) {

			q.push({i,cur.nd+1});

		}

	}

}

bool ok(int wait) {

	if(dis[1][s1]<dis[0][s1]+wait || dis[1][s2]<dis[0][s2]+wait) return false;

	return true;

}

void fdag(int node,int w,int val,int ata) {

	if(dis[2][node]!=val || dis[3][node]!=val) return ;

	nodes[w][node]=1;

	dag[w][ata].pb(node);

	for(int i:v[node]) {

		fdag(i,w,val-1,node);

	}

}

int fdep(int node,int w) {

	if(frb[node]) return 0;

	if(vdag[w][node]) return dep[w][node];

	dep[w][node]=1;

	vdag[w][node]=1;

	for(int i:dag[w][node]) {

//		cout<<node<<" "<<i<<"\n";

		umax(dep[w][node],fdep(i,w)+1);

	}

	return dep[w][node];

}

bool ok2(int val) {

	fdag(cur0,0,min(dis[2][cur0],dis[3][cur0]),0);
	fdag(cur,1,min(dis[2][cur],dis[3][cur]),0);

	int dep0=fdep(0,0);
	int dep1=fdep(0,1);

	if(dep1+val>=dep0) return true;

	for(int i=1;i<=n;i++) {

		if(nodes[1][i]) frb[i]=1;

	}

	memset(vdag[0],0,sizeof(vdag[0]));

	int dep0new=fdep(0,0);

	if(dep0new!=dep0) return true;

	return false;

}

int main() {

	//freopen("input.txt","r",stdin);

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>m;

	cin>>cur>>cur0>>s1>>s2;

	for(int i=1;i<=m;i++) {

		cin>>x>>y;

		v[x].pb(y);
		v[y].pb(x);

	}

	bfs(cur,0);
	bfs(cur0,1);

	int bas=0,son=m;

	while(bas<=son) {

		if(ok(orta)) bas=orta+1;
		else son=orta-1;

	}

	if(son==-1) {

		cout<<-1;

		return 0;

	}

	bfs(s1,2);
	bfs(s2,3);

	if(!ok2(son)) son--;

	cout<<son;

}

• Subtask 1: 16 / 30
• Subtask 2: 0 / 70