Submission #30008

#	Time	Username	Problem	Language	Result	Execution time	Memory
30008		PrOAhMeT	007 (CEOI14_007)	C++14	30 / 100	1000 ms	19932 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;
bool vis[MAXN];
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) {

	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",&t,&tt);
		v[t].pb(tt);
		v[tt].pb(t);
	}
	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:25: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:40: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:57:6: warning: unused variable 'l' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
      ^
007.cpp:57:10: warning: unused variable 'r' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
          ^
007.cpp:57:14: warning: unused variable 'ans' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
              ^
007.cpp:57:21: warning: unused variable 'md' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
                     ^
007.cpp:50: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:51: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:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&t,&tt);
                        ^

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