| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125802 |
2019-07-06T11:44:05 Z |
lyc |
007 (CEOI14_007) |
C++14 |
|
366 ms |
25080 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) ans -= 1;
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5116 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
6 ms |
5116 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5140 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 16 |
Correct |
7 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 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 20 |
Correct |
7 ms |
5116 KB |
Output is correct |
| 21 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 22 |
Correct |
7 ms |
5116 KB |
Output is 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 |
Correct |
36 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
54 ms |
8572 KB |
Output is correct |
| 3 |
Correct |
44 ms |
7544 KB |
Output is correct |
| 4 |
Correct |
48 ms |
8568 KB |
Output is correct |
| 5 |
Correct |
34 ms |
7288 KB |
Output is correct |
| 6 |
Correct |
40 ms |
7672 KB |
Output is correct |
| 7 |
Correct |
40 ms |
7928 KB |
Output is correct |
| 8 |
Correct |
41 ms |
7928 KB |
Output is correct |
| 9 |
Correct |
53 ms |
8824 KB |
Output is correct |
| 10 |
Correct |
180 ms |
17372 KB |
Output is correct |
| 11 |
Correct |
80 ms |
10360 KB |
Output is correct |
| 12 |
Correct |
105 ms |
11868 KB |
Output is correct |
| 13 |
Correct |
97 ms |
10872 KB |
Output is correct |
| 14 |
Correct |
72 ms |
9848 KB |
Output is correct |
| 15 |
Correct |
109 ms |
11896 KB |
Output is correct |
| 16 |
Correct |
116 ms |
12408 KB |
Output is correct |
| 17 |
Correct |
106 ms |
11512 KB |
Output is correct |
| 18 |
Correct |
99 ms |
11512 KB |
Output is correct |
| 19 |
Correct |
137 ms |
13944 KB |
Output is correct |
| 20 |
Correct |
242 ms |
19832 KB |
Output is correct |
| 21 |
Correct |
262 ms |
14692 KB |
Output is correct |
| 22 |
Correct |
142 ms |
13312 KB |
Output is correct |
| 23 |
Correct |
174 ms |
14468 KB |
Output is correct |
| 24 |
Correct |
172 ms |
14456 KB |
Output is correct |
| 25 |
Correct |
149 ms |
13972 KB |
Output is correct |
| 26 |
Correct |
137 ms |
13432 KB |
Output is correct |
| 27 |
Correct |
182 ms |
14576 KB |
Output is correct |
| 28 |
Correct |
202 ms |
14556 KB |
Output is correct |
| 29 |
Correct |
190 ms |
16460 KB |
Output is correct |
| 30 |
Correct |
260 ms |
20888 KB |
Output is correct |
| 31 |
Correct |
215 ms |
15992 KB |
Output is correct |
| 32 |
Correct |
177 ms |
14580 KB |
Output is correct |
| 33 |
Correct |
165 ms |
14844 KB |
Output is correct |
| 34 |
Correct |
193 ms |
15352 KB |
Output is correct |
| 35 |
Correct |
183 ms |
14844 KB |
Output is correct |
| 36 |
Correct |
191 ms |
15452 KB |
Output is correct |
| 37 |
Correct |
281 ms |
16712 KB |
Output is correct |
| 38 |
Correct |
292 ms |
16376 KB |
Output is correct |
| 39 |
Correct |
321 ms |
16376 KB |
Output is correct |
| 40 |
Correct |
310 ms |
20088 KB |
Output is correct |
| 41 |
Correct |
366 ms |
25080 KB |
Output is correct |
