답안 #30002 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30002	2017-07-21T11:54:34 Z	cdemirer	007 (CEOI14_007)	C++14	0 / 100	1000 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) && ans != minsv) if (best1 != best2) ans--;
	else if (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:109:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
  if (ans == min(best1, best2) && ans != minsv) if (best1 != best2) ans--;
     ^
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.0 / 30.0

#	결과	메모리	Grader output
1	Correct	5540 KB	Output is correct
2	Correct	5540 KB	Output is correct
3	Correct	5540 KB	Output is correct
4	Incorrect	5540 KB	Output isn't correct
5	Incorrect	5540 KB	Output isn't correct
6	Correct	5540 KB	Output is correct
7	Correct	5540 KB	Output is correct
8	Incorrect	5540 KB	Output isn't 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	Incorrect	5540 KB	Output isn't correct
17	Incorrect	5672 KB	Output isn't 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	Incorrect	5672 KB	Output isn't correct

Subtask #2
0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	9664 KB	Output is correct
2	Incorrect	133 ms	11552 KB	Output isn't correct
3	Correct	129 ms	9980 KB	Output is correct
4	Incorrect	133 ms	11736 KB	Output isn't correct
5	Correct	89 ms	9484 KB	Output is correct
6	Correct	96 ms	10156 KB	Output is correct
7	Correct	113 ms	10520 KB	Output is correct
8	Correct	116 ms	10520 KB	Output is correct
9	Incorrect	153 ms	11072 KB	Output isn't correct
10	Correct	283 ms	15952 KB	Output is correct
11	Incorrect	349 ms	14792 KB	Output isn't correct
12	Correct	476 ms	17032 KB	Output is correct
13	Incorrect	403 ms	15480 KB	Output isn't correct
14	Correct	289 ms	13940 KB	Output is correct
15	Correct	313 ms	17364 KB	Output is correct
16	Correct	519 ms	17908 KB	Output is correct
17	Correct	429 ms	16680 KB	Output is correct
18	Incorrect	449 ms	16680 KB	Output isn't correct
19	Correct	413 ms	17912 KB	Output is correct
20	Incorrect	449 ms	20908 KB	Output isn't correct
21	Incorrect	706 ms	21852 KB	Output isn't correct
22	Correct	609 ms	19616 KB	Output is correct
23	Correct	663 ms	21660 KB	Output is correct
24	Correct	656 ms	21496 KB	Output is correct
25	Incorrect	673 ms	20636 KB	Output isn't correct
26	Correct	636 ms	19800 KB	Output is correct
27	Correct	739 ms	21836 KB	Output is correct
28	Correct	753 ms	21840 KB	Output is correct
29	Correct	646 ms	21088 KB	Output is correct
30	Incorrect	829 ms	22584 KB	Output isn't correct
31	Incorrect	863 ms	24256 KB	Output isn't correct
32	Correct	789 ms	21652 KB	Output is correct
33	Correct	779 ms	22196 KB	Output is correct
34	Incorrect	849 ms	23024 KB	Output isn't correct
35	Incorrect	659 ms	22360 KB	Output isn't correct
36	Incorrect	453 ms	23036 KB	Output isn't correct
37	Correct	686 ms	25284 KB	Output is correct
38	Correct	603 ms	24916 KB	Output is correct
39	Correct	696 ms	24920 KB	Output is correct
40	Incorrect	989 ms	25892 KB	Output isn't correct
41	Execution timed out	1000 ms	27752 KB	Execution timed out

답안 #30002

Compilation message

Subtask #1 0.0 / 30.0

Subtask #2 0.0 / 70.0

Subtask #1
0.0 / 30.0

Subtask #2
0.0 / 70.0