답안 #29998 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29998	2017-07-21T11:50:45 Z	cdemirer	007 (CEOI14_007)	C++14	10 / 100	939 ms	27752 KB

#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 flag[200000] = {0};
bool flag2[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 best1 = -1;
	int best2 = -1;
	int x = Dparents[SV1];
	flag[SV1] = flag[SV2] = true;
	while (x != -1) {
		//if (x) cerr << x << endl;
		int fark = Ddists[x] - Zdists[x];
		best1 = max(best1, fark);
		x = Dparents[x];
		flag[x] = true;
	}
	x = Dparents[SV2];
	int cntD = 1;
	while (x != -1) {
		if (flag[x] != true) cntD++;
		int fark = Ddists[x] - Zdists[x];
		best2 = max(best2, fark);
		x = Dparents[x];
	}
	x = Zparents[SV1];
	int cntZ = 1;
	while (x != -1) {
		flag2[x] = true;
		x = Zparents[x];
	}
	x = Zparents[SV2];
	while (x != -1) {
		if (flag2[x] != true) cntZ++;
		x = Zparents[x];
	}
	int sv1 = Ddists[SV1] - Zdists[SV1];
	int sv2 = Ddists[SV2] - Zdists[SV2];
	int minsv = min(sv1, sv2);
	int ans = -1;
	ans = max(ans, min(best1, best2));
	ans = max(ans, minsv);
	
	//if (Dparents[SV1] == SV2) best1 = max(best1, Ddists[SV1] - Zdists[SV1] - 2);
	//if (Dparents[SV2] == SV1) best2 = max(best2, Ddists[SV2] - Zdists[SV2] - 2);
	//int ans = min(best1, best2);
	//if (Dparents[SV1] != SV2 && Dparents[SV2] != SV1 && min(best1, best2) != ans) ans = (ans!=-1?ans-1:-1);
	if (ans != min(best1, best2) && Dparents[SV1] != SV2 && Dparents[SV2] != SV1 && Zparents[SV1] != SV2 && Zparents[SV2] != SV1 && cntD < cntZ) ans--;
	printf("%d\n", (ans!=-1?ans:-1));

	return 0;
}

Compilation message

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
3.0 / 30.0

#	결과	메모리	Grader output
1	Partially correct	5540 KB	Partially correct
2	Correct	5540 KB	Output is correct
3	Correct	5540 KB	Output is correct
4	Correct	5540 KB	Output is correct
5	Correct	5540 KB	Output is correct
6	Correct	5540 KB	Output is correct
7	Correct	5540 KB	Output is correct
8	Correct	5540 KB	Output is correct
9	Correct	5540 KB	Output is correct
10	Correct	5540 KB	Output is correct
11	Correct	5540 KB	Output is correct
12	Incorrect	5540 KB	Output isn't correct
13	Correct	5672 KB	Output is correct
14	Incorrect	5540 KB	Output isn't correct
15	Correct	5540 KB	Output is correct
16	Correct	5540 KB	Output is correct
17	Correct	5672 KB	Output is correct
18	Incorrect	5672 KB	Output isn't correct
19	Correct	5672 KB	Output is correct
20	Correct	5672 KB	Output is correct
21	Correct	5672 KB	Output is correct
22	Correct	5672 KB	Output is correct
23	Correct	5672 KB	Output is correct
24	Correct	5672 KB	Output is correct

Subtask #2
7.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	9664 KB	Output is correct
2	Correct	179 ms	11552 KB	Output is correct
3	Partially correct	143 ms	9980 KB	Partially correct
4	Correct	176 ms	11736 KB	Output is correct
5	Correct	99 ms	9484 KB	Output is correct
6	Correct	136 ms	10156 KB	Output is correct
7	Correct	133 ms	10520 KB	Output is correct
8	Correct	146 ms	10520 KB	Output is correct
9	Correct	169 ms	11072 KB	Output is correct
10	Correct	353 ms	15952 KB	Output is correct
11	Correct	359 ms	14792 KB	Output is correct
12	Correct	496 ms	17032 KB	Output is correct
13	Correct	386 ms	15480 KB	Output is correct
14	Correct	299 ms	13940 KB	Output is correct
15	Correct	496 ms	17364 KB	Output is correct
16	Correct	423 ms	17908 KB	Output is correct
17	Correct	423 ms	16680 KB	Output is correct
18	Incorrect	469 ms	16680 KB	Output isn't correct
19	Correct	476 ms	17912 KB	Output is correct
20	Correct	489 ms	20908 KB	Output is correct
21	Incorrect	643 ms	21852 KB	Output isn't correct
22	Partially correct	546 ms	19616 KB	Partially correct
23	Correct	639 ms	21660 KB	Output is correct
24	Partially correct	659 ms	21496 KB	Partially correct
25	Incorrect	646 ms	20636 KB	Output isn't correct
26	Correct	483 ms	19800 KB	Output is correct
27	Correct	746 ms	21836 KB	Output is correct
28	Correct	699 ms	21840 KB	Output is correct
29	Correct	613 ms	21088 KB	Output is correct
30	Correct	599 ms	22584 KB	Output is correct
31	Incorrect	679 ms	24256 KB	Output isn't correct
32	Correct	556 ms	21652 KB	Output is correct
33	Correct	736 ms	22196 KB	Output is correct
34	Incorrect	666 ms	23024 KB	Output isn't correct
35	Correct	646 ms	22360 KB	Output is correct
36	Correct	719 ms	23036 KB	Output is correct
37	Correct	739 ms	25284 KB	Output is correct
38	Correct	679 ms	24916 KB	Output is correct
39	Correct	609 ms	24920 KB	Output is correct
40	Correct	939 ms	25892 KB	Output is correct
41	Correct	909 ms	27752 KB	Output is correct

답안 #29998

Compilation message

Subtask #1 3.0 / 30.0

Subtask #2 7.0 / 70.0

Subtask #1
3.0 / 30.0

Subtask #2
7.0 / 70.0