Submission #30064

#	Time	Username	Problem	Language	Result	Execution time	Memory
30064		cdemirer	007 (CEOI14_007)	C++14	0 / 100	883 ms	27752 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 Ddists[200000], Zdists[200000];
int Dparents[200000], Zparents[200000];

void dijsktra(int *dists, int s) {
	set<ii> S;
	for (int i = 0; i < N; i++) {
		if (i == s) {
			dists[i] = 0;
			S.insert(mp(dists[i], i));
			continue;
		}
		dists[i] = (int)1e9;
		S.insert(mp(dists[i], i));
	}
	while ( ! S.empty() ) {
		ii x = *S.begin();
		S.erase(S.begin());
		for (int i = 0; i < edges[x.second].size(); i++) {
			if (dists[x.second] + 1 < dists[edges[x.second][i]]) {
				S.erase(mp(dists[edges[x.second][i]], edges[x.second][i]));
				dists[edges[x.second][i]] = dists[x.second] + 1;
				if (s == D) Dparents[edges[x.second][i]] = x.second;
				else Zparents[edges[x.second][i]] = x.second;
				S.insert(mp(dists[edges[x.second][i]], edges[x.second][i]));
			}
		}
	}
}

bool flagD[200000] = {0};
bool flagZ[200000] = {0};

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);
	}
	Dparents[D] = -1;
	dijsktra(Ddists, D);
	Zparents[Z] = -1;
	dijsktra(Zdists, Z);

	int ans = -1;
	if (Ddists[SV1] == Ddists[SV2]) {
		int svd = min(Ddists[SV1]-Zdists[SV1], Ddists[SV2]-Zdists[SV2]);
		ans = max(ans, svd);
		if (Zdists[SV1] == Zdists[SV2]) {
			int fakeD = 0, fakeZ = 0;
			int x = SV1;
			while (x != -1) {
				flagD[x] = true;
				x = Dparents[x];
			}
			x = SV2;
			while (x != -1) {
				if (!flagD[x]) fakeD++;
				else break;
				x = Dparents[x];
			}
			x = SV1;
			while (x != -1) {
				flagZ[x] = true;
				x = Zparents[x];
			}
			x = SV2;
			while (x != -1) {
				if (!flagZ[x]) fakeZ++;
				else break;
				x = Zparents[x];
			}
			if (fakeD + (svd!=-1?svd:0) < fakeZ) {
				if (ans != -1) ans--;
			}
		}
	}
	else {
		if (Ddists[SV1] < Ddists[SV2]) {
			ans = max(ans, Ddists[SV1] - Zdists[SV1]);
		}
		else {
			ans = max(ans, Ddists[SV2] - Zdists[SV2]);
		}
	}
	printf("%d\n", ans);

	return 0;
}

Compilation message (stderr)

007.cpp: In function 'void dijsktra(int*, int)':
007.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x.second].size(); i++) {
                     ^
007.cpp: In function 'int main(int, char**)':
007.cpp:53: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:54: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:58: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: 0 / 30
• Subtask 2: 0 / 70