| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125722 |
2019-07-06T09:26:10 Z |
lyc |
007 (CEOI14_007) |
C++14 |
|
345 ms |
22136 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 2e5+5;
int N,M,S,D,A,B;
vector<int> al[MAXN];
int dS[MAXN], dD[MAXN], dA[MAXN], dB[MAXN];
void bfs(int x, int d[]) {
FOR(i,1,N) d[i] = -1;
queue<int> q;
d[x] = 0; q.push(x);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto v : al[u]) if (d[v] == -1) d[v] = d[u]+1, q.push(v);
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
cin >> S >> D >> A >> B;
FOR(i,1,M){
int U, V; cin >> U >> V;
al[U].push_back(V);
al[V].push_back(U);
}
bfs(S, dS);
bfs(D, dD);
bfs(A, dA);
bfs(B, dB);
if (dS[A] > dD[A] || dS[B] > dD[B]) cout << -1 << '\n';
else {
int ans = min(dD[A]-dS[A], dD[B]-dS[B]);
int sS = S, sD = D;
FOR(i,1,N) {
if (dS[i] + dA[i] == dS[A] && dS[i] + dB[i] == dS[B]) sS = (dS[sS] > dS[i] ? sS : i);
if (dD[i] + dA[i] == dD[A] && dD[i] + dB[i] == dD[B]) sD = (dD[sD] > dD[i] ? sD : i);
}
//cout << ans << " :: " << sS << " " << sD << endl;
//if (sS != sD && dS[sS] < dD[sD]) ans -= 1;
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 6 |
Correct |
6 ms |
5084 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 8 |
Incorrect |
6 ms |
5116 KB |
Output isn't correct |
| 9 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 10 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 11 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 12 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 13 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 14 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 15 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 16 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 17 |
Incorrect |
7 ms |
5088 KB |
Output isn't correct |
| 18 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 19 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 20 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 21 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 22 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 23 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 24 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
7544 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
8492 KB |
Output isn't correct |
| 3 |
Correct |
35 ms |
7672 KB |
Output is correct |
| 4 |
Incorrect |
48 ms |
8648 KB |
Output isn't correct |
| 5 |
Correct |
34 ms |
7416 KB |
Output is correct |
| 6 |
Correct |
34 ms |
7672 KB |
Output is correct |
| 7 |
Correct |
39 ms |
7928 KB |
Output is correct |
| 8 |
Correct |
42 ms |
7928 KB |
Output is correct |
| 9 |
Incorrect |
51 ms |
8824 KB |
Output isn't correct |
| 10 |
Correct |
174 ms |
16760 KB |
Output is correct |
| 11 |
Incorrect |
80 ms |
10488 KB |
Output isn't correct |
| 12 |
Correct |
102 ms |
11768 KB |
Output is correct |
| 13 |
Incorrect |
83 ms |
10872 KB |
Output isn't correct |
| 14 |
Correct |
64 ms |
9848 KB |
Output is correct |
| 15 |
Correct |
167 ms |
11996 KB |
Output is correct |
| 16 |
Correct |
125 ms |
12280 KB |
Output is correct |
| 17 |
Correct |
121 ms |
11512 KB |
Output is correct |
| 18 |
Incorrect |
112 ms |
11512 KB |
Output isn't correct |
| 19 |
Correct |
134 ms |
13944 KB |
Output is correct |
| 20 |
Incorrect |
243 ms |
18808 KB |
Output isn't correct |
| 21 |
Incorrect |
163 ms |
14700 KB |
Output isn't correct |
| 22 |
Correct |
126 ms |
13304 KB |
Output is correct |
| 23 |
Correct |
126 ms |
14456 KB |
Output is correct |
| 24 |
Correct |
168 ms |
14308 KB |
Output is correct |
| 25 |
Incorrect |
151 ms |
13828 KB |
Output isn't correct |
| 26 |
Correct |
154 ms |
13432 KB |
Output is correct |
| 27 |
Correct |
177 ms |
14712 KB |
Output is correct |
| 28 |
Correct |
196 ms |
14640 KB |
Output is correct |
| 29 |
Correct |
196 ms |
16408 KB |
Output is correct |
| 30 |
Incorrect |
261 ms |
19416 KB |
Output isn't correct |
| 31 |
Incorrect |
185 ms |
15992 KB |
Output isn't correct |
| 32 |
Correct |
172 ms |
14684 KB |
Output is correct |
| 33 |
Correct |
201 ms |
14940 KB |
Output is correct |
| 34 |
Incorrect |
186 ms |
15352 KB |
Output isn't correct |
| 35 |
Incorrect |
177 ms |
14992 KB |
Output isn't correct |
| 36 |
Incorrect |
188 ms |
15356 KB |
Output isn't correct |
| 37 |
Correct |
221 ms |
16668 KB |
Output is correct |
| 38 |
Correct |
226 ms |
16376 KB |
Output is correct |
| 39 |
Correct |
345 ms |
16472 KB |
Output is correct |
| 40 |
Incorrect |
321 ms |
19984 KB |
Output isn't correct |
| 41 |
Correct |
333 ms |
22136 KB |
Output is correct |
