Submission #712930

#	Time	Username	Problem	Language	Result	Execution time	Memory
712930		yuseok0803	007 (CEOI14_007)	C++14	20 / 100	1105 ms	524288 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];

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

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

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

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