Submission #110514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
110514	2019-05-11T05:26:39 Z	ckodser	007 (CEOI14_007)	C++14	0 / 100	497 ms	54264 KB

007

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 200005;
int n, m, a, b, s1, s2, D[2][N], F[N], P[N];
vector < int > vec[N], Adj[N];
inline void BFS(int st, int w, int tp = 0)
{
	queue < int > qu;
	qu.push(st); D[w][st] = 0;
	while (qu.size())
	{
		int v = qu.front();
		qu.pop();
		if (tp) vec[D[w][v]].pb(v);
		for (int &u : Adj[v])
			if (D[w][u] == -1)
				D[w][u] = D[w][v] + 1, qu.push(u);
	}
}
inline bool Check(int s, int t)
{
	if (D[0][t] < D[0][s] || D[1][t] < D[1][s])
		return 0;
	if (D[0][s] < D[0][t] || D[1][s] < D[1][t])
		return 1;
	return (F[s] <= F[t]);
}
inline bool CMP(int i, int j)
{
	return (D[0][i] <= D[0][j]);
}
int main()
{
	scanf("%d%d%d%d%d%d", &n, &m, &s1, &s2, &a, &b);
	for (int i = 0; i < m; i++)
	{
		int v, u;
		scanf("%d%d", &v, &u);
		Adj[v].pb(u);
		Adj[u].pb(v);
	}
	memset(D, -1, sizeof(D));
	BFS(s2, 0, 1);
	memset(D, -1, sizeof(D));
	BFS(a, 0); BFS(b, 1);
	memset(F, 63, sizeof(F));
	for (int i = 1; i <= n; i++)
		P[i] = i;
	sort(P + 1, P + n + 1, CMP);
	for (int i = 1; i <= n; i++)
	{
		int v = P[i];
		if (D[0][v] == D[1][v])
		{
			F[v] = D[0][v];
			for (int u : Adj[v])
				if (D[0][v] == D[0][u] + 1 && D[1][v] == D[1][u] + 1)
					F[v] = min(F[v], F[u]);
		}
	}
	for (int i = 0; ; i ++)
		for (int v : vec[i])
			if (!Check(s1, v))
				return !printf("%d\n", i - 1);
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d%d", &n, &m, &s1, &s2, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v, &u);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	12 ms	12160 KB	Output is correct
3	Correct	13 ms	12032 KB	Output is correct
4	Correct	13 ms	12032 KB	Output is correct
5	Correct	12 ms	12108 KB	Output is correct
6	Correct	13 ms	12032 KB	Output is correct
7	Correct	15 ms	12160 KB	Output is correct
8	Runtime error	30 ms	24064 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	17 ms	12132 KB	Output is correct
10	Correct	13 ms	12160 KB	Output is correct
11	Correct	13 ms	12160 KB	Output is correct
12	Correct	13 ms	12032 KB	Output is correct
13	Correct	13 ms	12032 KB	Output is correct
14	Runtime error	27 ms	24056 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Correct	14 ms	12160 KB	Output is correct
16	Correct	10 ms	12152 KB	Output is correct
17	Correct	15 ms	12160 KB	Output is correct
18	Correct	15 ms	12132 KB	Output is correct
19	Correct	14 ms	12184 KB	Output is correct
20	Correct	13 ms	12032 KB	Output is correct
21	Correct	18 ms	12024 KB	Output is correct
22	Correct	14 ms	12032 KB	Output is correct
23	Correct	14 ms	12132 KB	Output is correct
24	Runtime error	34 ms	24056 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2

0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	14200 KB	Output is correct
2	Correct	73 ms	15444 KB	Output is correct
3	Correct	101 ms	14328 KB	Output is correct
4	Correct	80 ms	15480 KB	Output is correct
5	Correct	68 ms	14200 KB	Output is correct
6	Correct	53 ms	14584 KB	Output is correct
7	Correct	84 ms	14600 KB	Output is correct
8	Correct	85 ms	14840 KB	Output is correct
9	Runtime error	89 ms	29900 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	233 ms	42808 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Correct	112 ms	17016 KB	Output is correct
12	Correct	272 ms	18200 KB	Output is correct
13	Correct	172 ms	17272 KB	Output is correct
14	Correct	129 ms	16428 KB	Output is correct
15	Correct	161 ms	18204 KB	Output is correct
16	Correct	162 ms	18728 KB	Output is correct
17	Correct	143 ms	17948 KB	Output is correct
18	Correct	196 ms	17872 KB	Output is correct
19	Runtime error	181 ms	38396 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	264 ms	46328 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Correct	163 ms	20984 KB	Output is correct
22	Correct	211 ms	19576 KB	Output is correct
23	Correct	178 ms	20808 KB	Output is correct
24	Correct	216 ms	20728 KB	Output is correct
25	Correct	229 ms	20088 KB	Output is correct
26	Correct	217 ms	19576 KB	Output is correct
27	Correct	250 ms	20600 KB	Output is correct
28	Correct	316 ms	20728 KB	Output is correct
29	Runtime error	189 ms	42256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	378 ms	47860 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Correct	228 ms	22392 KB	Output is correct
32	Correct	376 ms	20700 KB	Output is correct
33	Correct	229 ms	20984 KB	Output is correct
34	Correct	361 ms	21496 KB	Output is correct
35	Correct	211 ms	21368 KB	Output is correct
36	Correct	235 ms	22136 KB	Output is correct
37	Correct	318 ms	22524 KB	Output is correct
38	Correct	304 ms	22232 KB	Output is correct
39	Correct	497 ms	22264 KB	Output is correct
40	Runtime error	303 ms	47736 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	466 ms	54264 KB	Execution killed with signal 11 (could be triggered by violating memory limits)