답안 #110516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110516	2019-05-11T05:30:15 Z	ckodser	007 (CEOI14_007)	C++14	0 / 100	537 ms	140876 KB

007

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1000006;
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 <= n; 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

#	결과	실행 시간	메모리	Grader output
1	Correct	62 ms	59000 KB	Output is correct
2	Correct	60 ms	59000 KB	Output is correct
3	Correct	59 ms	59128 KB	Output is correct
4	Correct	58 ms	59000 KB	Output is correct
5	Correct	67 ms	59000 KB	Output is correct
6	Correct	63 ms	59036 KB	Output is correct
7	Correct	60 ms	59000 KB	Output is correct
8	Runtime error	129 ms	117880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Correct	59 ms	59128 KB	Output is correct
10	Correct	66 ms	59092 KB	Output is correct
11	Correct	61 ms	59000 KB	Output is correct
12	Correct	101 ms	59092 KB	Output is correct
13	Correct	67 ms	59128 KB	Output is correct
14	Runtime error	138 ms	117880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Correct	64 ms	59004 KB	Output is correct
16	Correct	58 ms	59000 KB	Output is correct
17	Correct	62 ms	59132 KB	Output is correct
18	Correct	61 ms	59128 KB	Output is correct
19	Correct	60 ms	59128 KB	Output is correct
20	Correct	60 ms	59128 KB	Output is correct
21	Correct	60 ms	59000 KB	Output is correct
22	Correct	61 ms	59000 KB	Output is correct
23	Correct	64 ms	59132 KB	Output is correct
24	Runtime error	135 ms	117904 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2

0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	110 ms	60772 KB	Output is correct
2	Correct	112 ms	61560 KB	Output is correct
3	Correct	122 ms	60792 KB	Output is correct
4	Correct	125 ms	61760 KB	Output is correct
5	Correct	114 ms	60712 KB	Output is correct
6	Correct	99 ms	61048 KB	Output is correct
7	Correct	120 ms	61048 KB	Output is correct
8	Correct	138 ms	61048 KB	Output is correct
9	Runtime error	198 ms	123000 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	391 ms	131604 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Correct	171 ms	62712 KB	Output is correct
12	Correct	362 ms	63708 KB	Output is correct
13	Correct	224 ms	63224 KB	Output is correct
14	Correct	171 ms	62592 KB	Output is correct
15	Correct	199 ms	63736 KB	Output is correct
16	Correct	228 ms	64120 KB	Output is correct
17	Correct	207 ms	63480 KB	Output is correct
18	Correct	313 ms	63428 KB	Output is correct
19	Runtime error	285 ms	129912 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	417 ms	134552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Correct	259 ms	65912 KB	Output is correct
22	Correct	300 ms	64812 KB	Output is correct
23	Correct	244 ms	65784 KB	Output is correct
24	Correct	263 ms	65656 KB	Output is correct
25	Correct	326 ms	65144 KB	Output is correct
26	Correct	212 ms	64888 KB	Output is correct
27	Correct	262 ms	65760 KB	Output is correct
28	Correct	424 ms	65664 KB	Output is correct
29	Runtime error	360 ms	133040 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	435 ms	136008 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Correct	286 ms	67192 KB	Output is correct
32	Correct	389 ms	65788 KB	Output is correct
33	Correct	264 ms	65816 KB	Output is correct
34	Correct	404 ms	66168 KB	Output is correct
35	Correct	276 ms	66208 KB	Output is correct
36	Correct	254 ms	66936 KB	Output is correct
37	Correct	369 ms	67192 KB	Output is correct
38	Correct	393 ms	66892 KB	Output is correct
39	Correct	504 ms	66808 KB	Output is correct
40	Runtime error	411 ms	137276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	537 ms	140876 KB	Execution killed with signal 11 (could be triggered by violating memory limits)