Submission #30126

#	Time	Username	Problem	Language	Result	Execution time	Memory
30126		cdemirer	007 (CEOI14_007)	C++14	100 / 100	429 ms	18004 KiB

007

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

int N, M;
int Z, D, SV1, SV2;
vvi edges;
int sv1dists[200000], sv2dists[200000];
bool vis1[200000] = {0};
bool vis2[200000] = {0};

void bfs(int *dists, bool *vis, int st) {
	queue<int> Q;
	queue<int> Qt;
	int d = 0;
	Q.push(st);
	while (!Q.empty()) {
		while (!Q.empty()) {
			int x = Q.front();
			Q.pop();
			if (vis[x]) continue;
			dists[x] = d;
			vis[x] = true;
			for (int i = 0; i < edges[x].size(); i++) {
				if (vis[edges[x][i]]) continue;
				Qt.push(edges[x][i]);
			}
		}
		while (!Qt.empty()) {
			int x = Qt.front();
			Qt.pop();
			Q.push(x);
		}
		d++;
	}
}

int moveit(int x) {
	int cnt = 0;
	while (true) {
		bool fnd = false;
		for (int i = 0; i < edges[x].size(); i++) {
			int v = edges[x][i];
			if (sv1dists[v] == sv1dists[x]-1 && sv1dists[v] == sv2dists[v]) {
				fnd = true;
				x = v;
				break;
			}
		}
		if (!fnd) return cnt;
		else cnt++;
	}
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &N, &M);
	scanf("%d%d%d%d", &Z, &D, &SV1, &SV2);
	Z--; D--; SV1--; SV2--;
	edges.resize(N);
	for (int i = 0; i < M; i++) {
		int a, b; scanf("%d%d", &a, &b);
		a--, b--;
		edges[a].pb(b);
		edges[b].pb(a);
	}
	bfs(sv1dists, vis1, SV1);
	bfs(sv2dists, vis2, SV2);

	int ans = -1;
	ans = max(ans, min(sv1dists[D] - sv1dists[Z], sv2dists[D] - sv2dists[Z]));

	if (ans != -1 && sv1dists[D] == sv2dists[D] && sv1dists[Z] == sv2dists[Z]) {
		int a = moveit(D);
		int b = moveit(Z);
		if (a > b + ans) ans--;
	}
	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

007.cpp: In function 'void bfs(int*, bool*, int)':
007.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < edges[x].size(); i++) {
                      ^
007.cpp: In function 'int moveit(int)':
007.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                     ^
007.cpp: In function 'int main(int, char**)':
007.cpp:68:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
007.cpp:69:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &Z, &D, &SV1, &SV2);
                                       ^
007.cpp:73:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^

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