oj.uz

답안 #243254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243254 2020-06-30T16:08:31 Z BamiTorabi 007 (CEOI14_007) C++14
0 / 100
 355 ms 43640 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 Partially correct 9 ms 8192 KB Partially correct
3 Runtime error 26 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 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 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 21 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 18 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 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 18 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 9 ms 8192 KB Output is correct
15 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 18 ms 16416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 20 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 20 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 19 ms 16452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 19 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 19 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 20 ms 16384 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 54 ms 20728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 48 ms 19704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 55 ms 20984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 52 ms 19320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 44 ms 19668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 50 ms 19960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 50 ms 19960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 64 ms 21240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 200 ms 34040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 92 ms 23160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 116 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 110 ms 23672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 65 ms 11640 KB Output is correct
15 Runtime error 105 ms 25080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 108 ms 25592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 112 ms 24572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 146 ms 24544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 194 ms 28152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 264 ms 36728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 181 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 133 ms 26876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 165 ms 28280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 198 ms 28152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 149 ms 27640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 140 ms 27000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 166 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 174 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 195 ms 31480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 320 ms 38392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 234 ms 30328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 187 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 175 ms 28920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 200 ms 29560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 160 ms 28896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 165 ms 29432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 200 ms 31096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 234 ms 30968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 228 ms 30968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 289 ms 36472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 355 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)