| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125685 |
2019-07-06T08:36:22 Z |
lyc |
007 (CEOI14_007) |
C++14 |
|
352 ms |
24928 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 |
7 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 7 |
Partially correct |
8 ms |
4984 KB |
Partially correct |
| 8 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 9 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 10 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 11 |
Partially correct |
6 ms |
4984 KB |
Partially correct |
| 12 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 13 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 14 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 15 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 16 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 17 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 18 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 19 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 20 |
Partially correct |
8 ms |
5112 KB |
Partially correct |
| 21 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 22 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 23 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 24 |
Correct |
7 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
36 ms |
7416 KB |
Partially correct |
| 2 |
Correct |
45 ms |
8440 KB |
Output is correct |
| 3 |
Partially correct |
36 ms |
7544 KB |
Partially correct |
| 4 |
Correct |
49 ms |
8616 KB |
Output is correct |
| 5 |
Partially correct |
34 ms |
7416 KB |
Partially correct |
| 6 |
Partially correct |
36 ms |
7672 KB |
Partially correct |
| 7 |
Partially correct |
39 ms |
7928 KB |
Partially correct |
| 8 |
Correct |
41 ms |
7928 KB |
Output is correct |
| 9 |
Correct |
53 ms |
8824 KB |
Output is correct |
| 10 |
Partially correct |
177 ms |
17432 KB |
Partially correct |
| 11 |
Correct |
76 ms |
10360 KB |
Output is correct |
| 12 |
Partially correct |
101 ms |
11768 KB |
Partially correct |
| 13 |
Correct |
93 ms |
10872 KB |
Output is correct |
| 14 |
Correct |
66 ms |
9848 KB |
Output is correct |
| 15 |
Partially correct |
102 ms |
11896 KB |
Partially correct |
| 16 |
Partially correct |
116 ms |
12288 KB |
Partially correct |
| 17 |
Correct |
88 ms |
11384 KB |
Output is correct |
| 18 |
Correct |
97 ms |
11512 KB |
Output is correct |
| 19 |
Partially correct |
128 ms |
13952 KB |
Partially correct |
| 20 |
Correct |
283 ms |
19816 KB |
Output is correct |
| 21 |
Correct |
166 ms |
14584 KB |
Output is correct |
| 22 |
Partially correct |
155 ms |
13304 KB |
Partially correct |
| 23 |
Correct |
162 ms |
14412 KB |
Output is correct |
| 24 |
Partially correct |
165 ms |
14380 KB |
Partially correct |
| 25 |
Correct |
141 ms |
13852 KB |
Output is correct |
| 26 |
Correct |
128 ms |
13432 KB |
Output is correct |
| 27 |
Correct |
170 ms |
14584 KB |
Output is correct |
| 28 |
Correct |
189 ms |
14636 KB |
Output is correct |
| 29 |
Partially correct |
189 ms |
16356 KB |
Partially correct |
| 30 |
Correct |
246 ms |
20812 KB |
Output is correct |
| 31 |
Correct |
197 ms |
16120 KB |
Output is correct |
| 32 |
Partially correct |
194 ms |
14584 KB |
Partially correct |
| 33 |
Correct |
174 ms |
14972 KB |
Output is correct |
| 34 |
Correct |
201 ms |
15284 KB |
Output is correct |
| 35 |
Correct |
191 ms |
14820 KB |
Output is correct |
| 36 |
Correct |
198 ms |
15252 KB |
Output is correct |
| 37 |
Partially correct |
211 ms |
16732 KB |
Partially correct |
| 38 |
Correct |
274 ms |
16408 KB |
Output is correct |
| 39 |
Correct |
324 ms |
16504 KB |
Output is correct |
| 40 |
Correct |
274 ms |
20216 KB |
Output is correct |
| 41 |
Partially correct |
352 ms |
24928 KB |
Partially correct |
