oj.uz

답안 #490320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490320 2021-11-27T01:31:20 Z SirCovidThe19th 007 (CEOI14_007) C++17
30 / 100
 1000 ms 340388 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mx = 2e5 + 5;
 
int n, m, s, v, a, b, dA[mx], dB[mx], ans; vector<int> adj[mx];
 
void bfs(int st, int *D){
    queue<int> Q; fill(D, D + n + 1, -1); 
    Q.push(st); D[st] = 0;
    while (!Q.empty()){
        int i = Q.front(); Q.pop();
        for (int j : adj[i]) if (D[j] == -1) D[j] = D[i] + 1, Q.push(j);
    }
}
int nearer(int src){
	queue<int> Q; int D[n + 1], ret = 0; 
	D[src] = 0; Q.push(src);
	while (!Q.empty()){
		int i = Q.front(); Q.pop();
		ret = max(ret, D[i]);
		for (int j : adj[i]) if (dA[j] < dA[i] and dB[j] < dB[i]) D[j] = D[i] + 1, Q.push(j);
	}
	return ret;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> m >> s >> v >> a >> b;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    bfs(a, dA); bfs(b, dB);
    int wA = dA[v] - dA[s], wB = dB[v] - dB[s];
 
    if (wA == wB) ans = (nearer(s) >= nearer(v) - wA) ? wA : wA - 1;
    else ans = min(wA, wB);
 
    cout<<max(ans, -1)<<endl;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 2 ms 5068 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 2 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 3 ms 4992 KB Output is correct
18 Correct 2 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 5020 KB Output is correct
23 Correct 2 ms 4940 KB Output is correct
24 Correct 5 ms 5168 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 6860 KB Output is correct
2 Correct 21 ms 7688 KB Output is correct
3 Correct 17 ms 7028 KB Output is correct
4 Correct 23 ms 7756 KB Output is correct
5 Correct 16 ms 6732 KB Output is correct
6 Correct 17 ms 6936 KB Output is correct
7 Correct 19 ms 7212 KB Output is correct
8 Correct 20 ms 7284 KB Output is correct
9 Execution timed out 1101 ms 202712 KB Time limit exceeded
10 Execution timed out 1092 ms 340388 KB Time limit exceeded
11 Correct 36 ms 8876 KB Output is correct
12 Correct 57 ms 9868 KB Output is correct
13 Correct 50 ms 9204 KB Output is correct
14 Correct 37 ms 8424 KB Output is correct
15 Correct 46 ms 9988 KB Output is correct
16 Correct 53 ms 9680 KB Output is correct
17 Correct 46 ms 9644 KB Output is correct
18 Correct 45 ms 9680 KB Output is correct
19 Execution timed out 1102 ms 180992 KB Time limit exceeded
20 Execution timed out 1107 ms 239012 KB Time limit exceeded
21 Correct 72 ms 11980 KB Output is correct
22 Correct 63 ms 10960 KB Output is correct
23 Correct 67 ms 11756 KB Output is correct
24 Correct 65 ms 11684 KB Output is correct
25 Correct 63 ms 11332 KB Output is correct
26 Correct 58 ms 10972 KB Output is correct
27 Correct 71 ms 11848 KB Output is correct
28 Correct 85 ms 11904 KB Output is correct
29 Execution timed out 1084 ms 202692 KB Time limit exceeded
30 Execution timed out 1105 ms 229572 KB Time limit exceeded
31 Correct 77 ms 12888 KB Output is correct
32 Correct 87 ms 11696 KB Output is correct
33 Correct 73 ms 11964 KB Output is correct
34 Correct 86 ms 12292 KB Output is correct
35 Correct 69 ms 12072 KB Output is correct
36 Correct 83 ms 12372 KB Output is correct
37 Correct 91 ms 12512 KB Output is correct
38 Correct 97 ms 13168 KB Output is correct
39 Correct 114 ms 13132 KB Output is correct
40 Execution timed out 1103 ms 179788 KB Time limit exceeded
41 Execution timed out 1096 ms 199436 KB Time limit exceeded