oj.uz

답안 #243255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243255 2020-06-30T16:09:09 Z BamiTorabi 007 (CEOI14_007) C++14
0 / 100
 360 ms 36216 KB 
//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 2e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int dist[4][maxN];
queue <int> Q;
vector <int> G[maxN];

void BFS(int ix, int st){
	dist[ix][st] = 0;
	Q.push(st);
	while (!Q.empty()){
		int v = Q.front(); Q.pop();
		for (int u : G[v])
			if (dist[ix][u] > dist[ix][v] + 1){
				dist[ix][u] = dist[ix][v] + 1;
				Q.push(u);
			}
	}
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(dist, 63, sizeof dist);
	int n, m, s, t, a, b; scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
	while (m--){
		int u, v; scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	BFS(0, s);
	BFS(1, t);
	BFS(2, a);
	BFS(3, b);
	if (dist[2][t] < dist[2][s] || dist[3][t] < dist[b][s])
		return printf("-1\n"), 0;
	if (dist[2][t] - dist[2][s] != dist[3][t] - dist[3][s])
		return printf("%d\n", min(dist[2][t] - dist[2][s], dist[3][t] - dist[3][s])), 0;
	int mns = n, mnt = n;
	for (int i = 1; i <= n; i++){
		if (dist[0][i] + dist[2][i] == dist[2][s] && dist[0][i] + dist[3][i] == dist[3][s])
			mns = min(mns, dist[2][i]);
		if (dist[1][i] + dist[2][i] == dist[2][t] && dist[1][i] + dist[3][i] == dist[3][t])
			mnt = min(mnt, dist[3][i]);
	}
	printf("%d\n", dist[2][t] - dist[2][s] - (mnt > mns));
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:53:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, s, t, a, b; scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &a, &b);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 9 ms 8192 KB Output is correct
3 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 9 ms 8192 KB Output isn't correct
15 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 20 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 20 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 18 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 20 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 18 ms 16640 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 18936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 53 ms 20088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 45 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 55 ms 20216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 44 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 44 ms 19192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 49 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 48 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 64 ms 20344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 197 ms 28792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 81 ms 22136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 117 ms 23540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 93 ms 22520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 67 ms 10744 KB Output is correct
15 Runtime error 113 ms 23800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 117 ms 24164 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 100 ms 23288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 105 ms 23288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 151 ms 25720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 254 ms 31328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 151 ms 26488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 149 ms 25336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 174 ms 26488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 181 ms 26488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 161 ms 25720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 138 ms 25208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 155 ms 26616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 178 ms 26488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 191 ms 28152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 270 ms 32504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 184 ms 28028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 190 ms 26488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 163 ms 26744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 196 ms 27256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 157 ms 26872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 212 ms 27384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 264 ms 28792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 207 ms 28408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 216 ms 28380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 325 ms 31736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 360 ms 36216 KB Execution killed with signal 11 (could be triggered by violating memory limits)