oj.uz

Submission #243274

# Submission time Handle Problem Language Result Execution time Memory
243274 2020-06-30T16:45:01 Z BamiTorabi 007 (CEOI14_007) C++14
0 / 100
 335 ms 18040 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[3][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:54: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, &s, &t, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:56: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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8192 KB Output is correct
2 Correct 10 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Incorrect 9 ms 8192 KB Output isn't correct
5 Incorrect 9 ms 8192 KB Output isn't correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Incorrect 10 ms 8192 KB Output isn't correct
9 Correct 10 ms 8320 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Incorrect 9 ms 8192 KB Output isn't correct
13 Correct 9 ms 8192 KB Output is correct
14 Incorrect 10 ms 8192 KB Output isn't correct
15 Partially correct 9 ms 8192 KB Partially correct
16 Incorrect 10 ms 8192 KB Output isn't correct
17 Incorrect 9 ms 8192 KB Output isn't correct
18 Incorrect 10 ms 8192 KB Output isn't correct
19 Correct 10 ms 8192 KB Output is correct
20 Partially correct 10 ms 8192 KB Partially correct
21 Correct 10 ms 8192 KB Output is correct
22 Partially correct 9 ms 8192 KB Partially correct
23 Correct 10 ms 8192 KB Output is correct
24 Incorrect 10 ms 8192 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 34 ms 9472 KB Partially correct
2 Incorrect 43 ms 9976 KB Output isn't correct
3 Correct 37 ms 9464 KB Output is correct
4 Incorrect 58 ms 10104 KB Output isn't correct
5 Correct 36 ms 9344 KB Output is correct
6 Correct 34 ms 9600 KB Output is correct
7 Partially correct 39 ms 9720 KB Partially correct
8 Partially correct 39 ms 9728 KB Partially correct
9 Incorrect 57 ms 10104 KB Output isn't correct
10 Correct 188 ms 14328 KB Output is correct
11 Incorrect 70 ms 11000 KB Output isn't correct
12 Correct 107 ms 11708 KB Output is correct
13 Incorrect 81 ms 11256 KB Output isn't correct
14 Correct 66 ms 10744 KB Output is correct
15 Partially correct 102 ms 11768 KB Partially correct
16 Correct 104 ms 12024 KB Output is correct
17 Partially correct 96 ms 11516 KB Partially correct
18 Incorrect 98 ms 11768 KB Output isn't correct
19 Correct 144 ms 12812 KB Output is correct
20 Incorrect 237 ms 15608 KB Output isn't correct
21 Incorrect 143 ms 13304 KB Output isn't correct
22 Correct 132 ms 12664 KB Output is correct
23 Partially correct 148 ms 13296 KB Partially correct
24 Correct 131 ms 13048 KB Output is correct
25 Incorrect 129 ms 12792 KB Output isn't correct
26 Partially correct 112 ms 12664 KB Partially correct
27 Partially correct 148 ms 13176 KB Partially correct
28 Partially correct 159 ms 13176 KB Partially correct
29 Correct 178 ms 13944 KB Output is correct
30 Incorrect 285 ms 16120 KB Output isn't correct
31 Incorrect 168 ms 13944 KB Output isn't correct
32 Correct 161 ms 13148 KB Output is correct
33 Correct 155 ms 13432 KB Output is correct
34 Incorrect 178 ms 13560 KB Output isn't correct
35 Incorrect 138 ms 13304 KB Output isn't correct
36 Incorrect 142 ms 13560 KB Output isn't correct
37 Correct 197 ms 14316 KB Output is correct
38 Partially correct 184 ms 14200 KB Partially correct
39 Partially correct 203 ms 14076 KB Partially correct
40 Incorrect 294 ms 15992 KB Output isn't correct
41 Correct 335 ms 18040 KB Output is correct