Submission #450122

#	Time	Username	Problem	Language	Result	Execution time	Memory
450122		vanic	007 (CEOI14_007)	C++14	100 / 100	344 ms	17096 KiB

007

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int maxn=2e5+5;
 
vector < int > ms[maxn];
int dist[2][maxn];
bool bio[2][2][maxn];
 
void bfs(int x, int ind){
	queue < int > q;
	q.push(x);
	dist[ind][x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(dist[ind][ms[x][i]]==-1){
				dist[ind][ms[x][i]]=dist[ind][x]+1;
				q.push(ms[x][i]);
			}
		}
	}
}

void siri(int x, int y, int z){
	bio[y][z][x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!bio[y][z][ms[x][i]] && dist[y][ms[x][i]]==dist[y][x]-1){
			siri(ms[x][i], y, z);
		}
	}
}
 
int main(){
	memset(dist, -1, sizeof(dist));
	int n, m;
	scanf("%d%d", &n, &m);
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	a--; b--; c--; d--;
	int x, y;
	for(int i=0; i<m; i++){
		scanf("%d%d", &x, &y);
		x--; y--;
		ms[x].push_back(y);
		ms[y].push_back(x);
	}
	bfs(a, 0);
	bfs(b, 1);
	if(dist[0][c]>dist[1][c] || dist[0][d]>dist[1][d]){
		printf("-1\n");
	}
	else{
		if(dist[0][c]-dist[1][c]==dist[0][d]-dist[1][d]){
			siri(c, 0, 0);
			siri(d, 0, 1);
			siri(c, 1, 0);
			siri(d, 1, 1);
			int mini[2]={(int)1e9, (int)1e9};
			int cvor[2];
			int val;
			for(int j=0; j<2; j++){
				for(int i=0; i<n; i++){
					if(bio[j][0][i] && bio[j][1][i]){
						val=dist[j][c]-dist[j][i];
						if(val<mini[j]){
							mini[j]=val;
							cvor[j]=i;
						}
						
					}
				}
			}
			int raz=dist[1][c]-dist[0][c];
			if(cvor[0]==cvor[1]){
				printf("%d\n", raz);
			}
			else{
				if(mini[0]<=mini[1]){
					printf("%d\n", raz);
				}
				else{
					printf("%d\n", raz-1);
				}
			}
		}
		else{
			printf("%d\n", min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]));
		}
	}
	return 0;
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d%d%d", &a, &b, &c, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

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