oj.uz

답안 #490319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490319 2021-11-27T01:30:08 Z SirCovidThe19th 007 (CEOI14_007) C++17
30 / 100
 1000 ms 284944 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(){
    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 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 2 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 2 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 2 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 2 ms 4940 KB Output is correct
15 Correct 2 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 4 ms 4952 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 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 5 ms 5196 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 6724 KB Output is correct
2 Correct 43 ms 7472 KB Output is correct
3 Correct 35 ms 6796 KB Output is correct
4 Correct 46 ms 7540 KB Output is correct
5 Correct 34 ms 6516 KB Output is correct
6 Correct 32 ms 6724 KB Output is correct
7 Correct 37 ms 6980 KB Output is correct
8 Correct 37 ms 7032 KB Output is correct
9 Execution timed out 1087 ms 190264 KB Time limit exceeded
10 Execution timed out 1103 ms 284944 KB Time limit exceeded
11 Correct 89 ms 9168 KB Output is correct
12 Correct 98 ms 10092 KB Output is correct
13 Correct 78 ms 9392 KB Output is correct
14 Correct 72 ms 8740 KB Output is correct
15 Correct 92 ms 10212 KB Output is correct
16 Correct 95 ms 9928 KB Output is correct
17 Correct 82 ms 9924 KB Output is correct
18 Correct 87 ms 9960 KB Output is correct
19 Execution timed out 1100 ms 169320 KB Time limit exceeded
20 Execution timed out 1108 ms 206344 KB Time limit exceeded
21 Correct 127 ms 12136 KB Output is correct
22 Correct 114 ms 11180 KB Output is correct
23 Correct 126 ms 11972 KB Output is correct
24 Correct 128 ms 11972 KB Output is correct
25 Correct 123 ms 11560 KB Output is correct
26 Correct 111 ms 11332 KB Output is correct
27 Correct 154 ms 12128 KB Output is correct
28 Correct 137 ms 12164 KB Output is correct
29 Execution timed out 1100 ms 188912 KB Time limit exceeded
30 Execution timed out 1109 ms 192232 KB Time limit exceeded
31 Correct 150 ms 13160 KB Output is correct
32 Correct 136 ms 11988 KB Output is correct
33 Correct 135 ms 12320 KB Output is correct
34 Correct 152 ms 12588 KB Output is correct
35 Correct 137 ms 12364 KB Output is correct
36 Correct 139 ms 12552 KB Output is correct
37 Correct 169 ms 12840 KB Output is correct
38 Correct 167 ms 13404 KB Output is correct
39 Correct 173 ms 13384 KB Output is correct
40 Execution timed out 1100 ms 149656 KB Time limit exceeded
41 Execution timed out 1095 ms 145712 KB Time limit exceeded