Submission #70958

#	Time	Username	Problem	Language	Result	Execution time	Memory
70958		spencercompton	007 (CEOI14_007)	C++17	100 / 100	409 ms	103804 KiB

007

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200000];
int n, m;
vector<int> use1;
vector<int> use2;
vector<bool> v;
vector<int> bfs(int src){
	vector<int> li;
	vector<int> ret;
	ret.resize(n);
	for(int i = 0; i<n; i++){
		ret[i] = -1;
	}
	li.push_back(src);
	ret[src] = 0;
	for(int i = 0; i<n; i++){
		int now = li[i];
		for(int j = 0; j<adj[now].size(); j++){
			int to = adj[now][j];
			if(ret[to]==-1){
				ret[to] = ret[now]+1;
				li.push_back(to);
			}
		}
	}
	return ret;
}
int dfs(int now){
	int ret = 1;
	v[now] = true;
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(use1[now]-1==use1[to] && use2[to]==use1[to] && !v[to]){
			ret = max(ret, 1 + dfs(to));
		}
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int s, d, h1, h2;
	cin >> s >> d >> h1 >> h2;
	s--;
	d--;
	h1--;
	h2--;
	for(int i = 0; i<m; i++){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<int> d1 = bfs(h1);
	vector<int> d2 = bfs(h2);
	int dest = -1;
	if(d1[d]!=d2[d]){
		if(d1[d]<d2[d]){
			dest = 1;
		}
		else{
			dest = 2;
		}
	}
	if(d1[s]!=d2[s]){
		if(d1[s]<d2[s]){
			dest = 2;
		}
		else{
			dest = 1;
		}
	}
	int dif1 = d1[d]-d1[s];
	int dif2 = d2[d]-d2[s];
	if(dest!=-1){
		int z = min(dif1,dif2);
		if(z<-1){
			z = -1;
		}
		cout << z << endl;
		return 0;
	}
	else{
		int ans = -1;
		use1 = d1;
		use2 = d2;
		v.clear();
		v.resize(n);
		int a = dfs(d);
		v.clear();
		v.resize(n);
		int b = dfs(s);
		for(int i = 0; i<=n; i++){
			if(i+b<a){
				if(i+d1[s]+1<=d1[d]){
					ans = i;
				}
			}
			else{
				if(i+d1[s]<=d1[d]){
					ans = i;
				}
			}
		}
		cout << ans << endl;
	}
}

Compilation message (stderr)

007.cpp: In function 'std::vector<int> bfs(int)':
007.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<adj[now].size(); j++){
                  ~^~~~~~~~~~~~~~~~
007.cpp: In function 'int dfs(int)':
007.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~

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