| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125733 |
2019-07-06T09:42:17 Z |
lyc |
007 (CEOI14_007) |
C++14 |
|
341 ms |
18936 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 (dS[A] == dS[B] && dD[A] == dD[B] && 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 |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 7 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 8 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 9 |
Partially correct |
7 ms |
4984 KB |
Partially correct |
| 10 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 13 |
Partially correct |
6 ms |
5116 KB |
Partially correct |
| 14 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 15 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 16 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 17 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 19 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 20 |
Partially correct |
6 ms |
5112 KB |
Partially correct |
| 21 |
Correct |
7 ms |
5240 KB |
Output is correct |
| 22 |
Partially correct |
7 ms |
5112 KB |
Partially correct |
| 23 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 24 |
Correct |
6 ms |
5116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
34 ms |
7416 KB |
Partially correct |
| 2 |
Correct |
47 ms |
8568 KB |
Output is correct |
| 3 |
Partially correct |
36 ms |
7672 KB |
Partially correct |
| 4 |
Correct |
53 ms |
8696 KB |
Output is correct |
| 5 |
Correct |
33 ms |
7416 KB |
Output is correct |
| 6 |
Correct |
35 ms |
7800 KB |
Output is correct |
| 7 |
Partially correct |
44 ms |
7928 KB |
Partially correct |
| 8 |
Correct |
40 ms |
7928 KB |
Output is correct |
| 9 |
Correct |
55 ms |
8568 KB |
Output is correct |
| 10 |
Partially correct |
177 ms |
13560 KB |
Partially correct |
| 11 |
Correct |
84 ms |
10048 KB |
Output is correct |
| 12 |
Partially correct |
104 ms |
11100 KB |
Partially correct |
| 13 |
Correct |
87 ms |
10360 KB |
Output is correct |
| 14 |
Correct |
65 ms |
9720 KB |
Output is correct |
| 15 |
Partially correct |
120 ms |
11256 KB |
Partially correct |
| 16 |
Correct |
110 ms |
11640 KB |
Output is correct |
| 17 |
Correct |
95 ms |
11092 KB |
Output is correct |
| 18 |
Correct |
97 ms |
10872 KB |
Output is correct |
| 19 |
Partially correct |
132 ms |
12152 KB |
Partially correct |
| 20 |
Correct |
232 ms |
15480 KB |
Output is correct |
| 21 |
Correct |
168 ms |
13476 KB |
Output is correct |
| 22 |
Partially correct |
137 ms |
12280 KB |
Partially correct |
| 23 |
Correct |
167 ms |
13276 KB |
Output is correct |
| 24 |
Partially correct |
137 ms |
13176 KB |
Partially correct |
| 25 |
Correct |
152 ms |
12960 KB |
Output is correct |
| 26 |
Correct |
128 ms |
12412 KB |
Output is correct |
| 27 |
Correct |
164 ms |
13272 KB |
Output is correct |
| 28 |
Correct |
196 ms |
13328 KB |
Output is correct |
| 29 |
Partially correct |
185 ms |
13820 KB |
Partially correct |
| 30 |
Correct |
281 ms |
16396 KB |
Output is correct |
| 31 |
Correct |
289 ms |
14456 KB |
Output is correct |
| 32 |
Partially correct |
243 ms |
13304 KB |
Partially correct |
| 33 |
Correct |
175 ms |
13688 KB |
Output is correct |
| 34 |
Correct |
257 ms |
13944 KB |
Output is correct |
| 35 |
Correct |
169 ms |
13560 KB |
Output is correct |
| 36 |
Correct |
201 ms |
14028 KB |
Output is correct |
| 37 |
Correct |
230 ms |
15008 KB |
Output is correct |
| 38 |
Correct |
211 ms |
14712 KB |
Output is correct |
| 39 |
Correct |
239 ms |
14720 KB |
Output is correct |
| 40 |
Correct |
257 ms |
16248 KB |
Output is correct |
| 41 |
Partially correct |
341 ms |
18936 KB |
Partially correct |
