Submission #101127

#	Time	Username	Problem	Language	Result	Execution time	Memory
101127		Bruteforceman	007 (CEOI14_007)	C++11	93 / 100	621 ms	21072 KiB

007

#include "bits/stdc++.h"
using namespace std;
int d[4][200010];
vector <int> g[200010];

void bfs(int src, int r) {
	queue <int> Q;
	Q.push(src);
	d[r][src] = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		for(auto i : g[x]) {
			if(d[r][i] == -1) {
				d[r][i] = d[r][x] + 1;
				Q.push(i);
			}		
		}
	}
}

int dp[200010], fn[200010];
typedef pair <int, int> pii;

int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	int s, t, a, b;
	scanf("%d %d %d %d", &s, &t, &a, &b);
	for(int i = 1; i <= m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].emplace_back(q);
		g[q].emplace_back(p);
	}
	memset(d, -1, sizeof d);
	bfs(s, 0);
	bfs(t, 1);
	if(d[1][a] > d[1][b]) swap(a, b);
	if(d[1][a] == d[1][b] && d[0][a] < d[0][b]) swap(a, b);
	bfs(a, 2);
	bfs(b, 3);

	int opt = d[1][a] - d[0][a];

	if(d[1][a] < d[0][a] || d[1][b] < d[0][b]) {
		printf("-1\n");
		exit(0);
	}
	if(d[1][a] != d[1][b] && d[0][a] != d[0][b]) {
		printf("%d\n", opt);
		exit(0);
	}
	vector <pii> v;
	for(int i = 1; i <= n; i++) {
		v.emplace_back(-d[0][i], i);
	}
	sort(v.begin(), v.end());

	for(int i = 0; i < v.size(); i++) {
		int x = v[i].second;
		for(int j : g[x]) {
			if(d[0][j] <= d[0][x]) continue;
			if(d[2][j] + d[0][j] == d[0][a] && d[3][j] + d[0][j] == d[0][b]) {
				dp[x] = max(dp[x], 1 + dp[j]);
			}
		}
	}
	v.clear();
	
	for(int i = 1; i <= n; i++) {
		v.emplace_back(-d[1][i], i);
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i++) {
		int x = v[i].second;
		for(int j : g[x]) {
			if(d[1][j] <= d[1][x]) continue;
			if(d[2][j] + d[1][j] == d[1][a] && d[3][j] + d[1][j] == d[1][b]) {
				fn[x] = max(fn[x], 1 + fn[j]);
			}
		}
	}
	if(dp[s] < fn[t] - opt) {
		printf("%d\n", opt - 1);
	} else {
		printf("%d\n", opt);
	}
	return 0;
}

Compilation message (stderr)

007.cpp: In function 'int main(int, const char**)':
007.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
007.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
007.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
007.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &s, &t, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

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