Submission #246194

#	Time	Username	Problem	Language	Result	Execution time	Memory
246194		mieszko11b	007 (CEOI14_007)	C++14	100 / 100	331 ms	18356 KiB

007

#include <bits/stdc++.h>

using namespace std;

int n, m;
int s, d, a, b;
vector<int> G[200007];
int dista[200007], distb[200007], dists[200007], distd[200007];
bool vis[200007];

void run_bfs(int w, int *dist) {
	memset(vis, 0, sizeof vis);
	vis[w] = 1;
	dist[w] = 0;
	queue<int> Q;
	Q.push(w);
	
	while(!Q.empty()) {
		int u=  Q.front();
		Q.pop();
		
		for(int v : G[u]) {
			if(!vis[v]) {
				vis[v] = 1;
				dist[v] = dist[u] + 1;
				Q.push(v);
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &s, &d, &a, &b);
	while(m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	
	run_bfs(s, dists);
	run_bfs(d, distd);
	run_bfs(a, dista);
	run_bfs(b, distb);
	int sa = dists[a], sb = dists[b];
	int da = distd[a], db = distd[b];
	
	if(sa != sb || da != db) {
		int val = min(da - sa, db - sb);
		if(val < 0) val = -1;
		
		printf("%d\n", val);
	} else {
		int fs = 0, fd = 0;
		for(int i = 1 ; i <= n ; i++) {
			if(dists[i] + dista[i] == sa && dists[i] + distb[i] == sb)
				fs = max(fs, dists[i]);
			if(distd[i] + dista[i] == da && distd[i] + distb[i] == db)
				fd = max(fd, distd[i]);
		}
		
		int val = min(da - sa, db - sb);
		if(sa - fs > da - fd)
			val--;
			
		if(val < 0) val = -1;
			
		printf("%d\n", val);
	}
	
	return 0;
}

Compilation message (stderr)

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

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