Submission #30011

#	Time	Username	Problem	Language	Result	Execution time	Memory
30011		PrOAhMeT	007 (CEOI14_007)	C++14	100 / 100	586 ms	23276 KiB

007

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=200005;
int n,m,dis[4][MAXN],s,d,a,b,t,tt,x,y,mx,aa,mx1,dd[MAXN],tmp[MAXN];
bool vis[MAXN];
pii edge[600005];
vector<int> v[MAXN];

inline void bfs(int start,int wait,int u) {

	memset(dis[u],-1,sizeof dis[u]);
	queue<int> q;
	dis[u][start]=0;
	q.push(start);
	while(!q.empty()) {
		x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();++i) {
			y=v[x][i];
			if(dis[u][y]==-1) {
				dis[u][y]=dis[u][x]+1;
				q.push(y);
			}
		}
	}

}

inline void go(int x) {

	if(vis[x])
		return;
	vis[x]=1;
	mx=max(mx,dis[aa][x]);
	for(int i=0;i<v[x].size();++i) {
		y=v[x][i];
		if(dis[2][y]<dis[2][x]&&dis[3][y]<dis[3][x])
			go(y);
	}

}

int main() {

	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&s,&d,&a,&b);
	for(int i=0;i<m;++i) {
		scanf("%d %d",&edge[i].st,&edge[i].nd);
		++dd[edge[i].st];
		++dd[edge[i].nd];
	}
	for(int i=1;i<=n;++i)
		v[i].resize(dd[i]);
	for(int i=0;i<m;++i) {
		x=edge[i].st;
		y=edge[i].nd;
		v[y][tmp[y]++]=x;
		v[x][tmp[x]++]=y;
	}
	int l=0,r=n,ans=-1,md;
	bfs(d,0,1);
	bfs(s,0,0);
	bfs(a,0,2);
	bfs(b,0,3);
	if(dis[0][a]>dis[1][a]||dis[0][b]>dis[1][b])
		cout<<-1<<endl;
	else if(!((dis[1][a]-dis[0][a]==dis[1][b]-dis[0][b])&&dis[0][a]==dis[0][b])){
		cout<<min(dis[1][a]-dis[0][a],dis[1][b]-dis[0][b])<<endl;
	}
	else {
		aa=0;
		go(s);
		mx1=mx;
		if(vis[a]==0||vis[b]==0) {
			memset(vis,0,sizeof vis);
			mx=0;
			aa=1;
			go(d);
			if(mx<=dis[1][a]-dis[0][a]+mx1)
				cout<<dis[1][a]-dis[0][a]<<endl;
			else cout<<dis[1][a]-dis[0][a]-1<<endl;
		}
		else cout<<dis[1][a]-dis[0][a]<<endl;
	}

}

Compilation message (stderr)

007.cpp: In function 'void bfs(int, int, int)':
007.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v[x].size();++i) {
                ^
007.cpp: In function 'void go(int)':
007.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();++i) {
               ^
007.cpp: In function 'int main()':
007.cpp:68:6: warning: unused variable 'l' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
      ^
007.cpp:68:10: warning: unused variable 'r' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
          ^
007.cpp:68:14: warning: unused variable 'ans' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
              ^
007.cpp:68:21: warning: unused variable 'md' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
                     ^
007.cpp:53:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
007.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&s,&d,&a,&b);
                                  ^
007.cpp:56:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&edge[i].st,&edge[i].nd);
                                         ^

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