Submission #712933

#	Time	Username	Problem	Language	Result	Execution time	Memory
712933		yuseok0803	007 (CEOI14_007)	C++14	100 / 100	243 ms	16236 KiB

007

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>  
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;

int n,m;
int s,d,a,b;
v(int) pushvec;
v(v(int)) vec;
int dista[200010], distb[200010];
int dpdiv[200010];

void spreada(int x){
	q(int) qu;
	qu.push(x);
	dista[x]=0;
	
	while(!qu.empty()){
		int now = qu.front();
		qu.pop();
		
		int sz = vec[now].size();
		fi(0,sz){
			int next = vec[now][i];
			if(dista[next]==-1){
				dista[next]=dista[now]+1;
				qu.push(next);
			}
		}
	}
	return;
}

void spreadb(int x){
	q(int) qu;
	qu.push(x);
	distb[x]=0;
	
	while(!qu.empty()){
		int now = qu.front();
		qu.pop();
		
		int sz = vec[now].size();
		fi(0,sz){
			int next = vec[now][i];
			if(distb[next]==-1){
				distb[next]=distb[now]+1;
				qu.push(next);
			}
		}
	}
	return;
}

int find(int now){
	if(dpdiv[now]) return dpdiv[now];
	
	int sz = vec[now].size();
	int ans = dista[now];
	fi(0,sz){
		int next = vec[now][i];
		if(dista[next]==dista[now]-1 && dista[next]==distb[next]){
			ans = min(ans, find(next));
		}
	}
	return dpdiv[now]=ans;
}

int main(void){
	scanf("%d%d%d%d%d%d",&n,&m,&s,&d,&a,&b);
	
	fi(0,n+1) vec.push_back(pushvec);
	fi(0,m){
		int s,e;
		scanf("%d%d",&s,&e);
		vec[s].push_back(e);
		vec[e].push_back(s);
	}
	
	fi(1,n+1){
		dista[i]=-1;
		distb[i]=-1;
	}
	
	spreada(a);
	spreadb(b);
	
	int ans = min(dista[d]-dista[s], distb[d]-distb[s]);
	if(dista[s]==distb[s] && distb[d]==distb[d]){
		int divds, divdd;
		divds = find(s);
		divdd = find(d);
		if(divds > divdd) ans--;
	}
	
	printf("%d\n", max(ans, -1));
	return 0;
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:111:35: warning: self-comparison always evaluates to true [-Wtautological-compare]
  111 |  if(dista[s]==distb[s] && distb[d]==distb[d]){
      |                           ~~~~~~~~^~~~~~~~~~
007.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d%d%d%d%d",&n,&m,&s,&d,&a,&b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d%d",&s,&e);
      |   ~~~~~^~~~~~~~~~~~~~

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