답안 #490313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490313	2021-11-27T00:36:34 Z	SirCovidThe19th	007 (CEOI14_007)	C++17	30 / 100	429 ms	16208 KB

007

#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 same(int pos){
    int d = 0;
    while (1){
        bool ok = 0;
        for (int i : adj[pos]) if (dA[i] < dA[pos] and dB[i] < dB[pos]){
            pos = i; ok = 1; d++; 
            break;
        }
        if (!ok) break;
    }
    return d;
}

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 = (same(s) < same(v) ? wA - 1 : wA);
    else ans = min(wA, wB);

    cout<<max(ans, -1)<<endl;
}

Subtask #1

9.0 / 30.0

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

Subtask #2

21.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	31 ms	6560 KB	Partially correct
2	Correct	42 ms	7228 KB	Output is correct
3	Partially correct	33 ms	6632 KB	Partially correct
4	Correct	43 ms	7360 KB	Output is correct
5	Correct	33 ms	6444 KB	Output is correct
6	Correct	33 ms	6724 KB	Output is correct
7	Partially correct	43 ms	6840 KB	Partially correct
8	Correct	35 ms	6784 KB	Output is correct
9	Correct	57 ms	7292 KB	Output is correct
10	Partially correct	250 ms	11604 KB	Partially correct
11	Correct	67 ms	8512 KB	Output is correct
12	Partially correct	93 ms	9320 KB	Partially correct
13	Correct	83 ms	8792 KB	Output is correct
14	Correct	83 ms	8124 KB	Output is correct
15	Partially correct	91 ms	9412 KB	Partially correct
16	Correct	105 ms	9656 KB	Output is correct
17	Correct	98 ms	9228 KB	Output is correct
18	Correct	104 ms	9152 KB	Output is correct
19	Partially correct	162 ms	10436 KB	Partially correct
20	Correct	284 ms	13268 KB	Output is correct
21	Correct	123 ms	11200 KB	Output is correct
22	Partially correct	118 ms	10340 KB	Partially correct
23	Partially correct	123 ms	11132 KB	Partially correct
24	Partially correct	119 ms	11032 KB	Partially correct
25	Correct	118 ms	10792 KB	Output is correct
26	Partially correct	108 ms	10444 KB	Partially correct
27	Correct	137 ms	11204 KB	Output is correct
28	Correct	134 ms	11204 KB	Output is correct
29	Partially correct	187 ms	11844 KB	Partially correct
30	Correct	309 ms	13764 KB	Output is correct
31	Correct	148 ms	12100 KB	Output is correct
32	Partially correct	132 ms	11136 KB	Partially correct
33	Partially correct	130 ms	11292 KB	Partially correct
34	Correct	142 ms	11636 KB	Output is correct
35	Correct	141 ms	11460 KB	Output is correct
36	Correct	170 ms	11644 KB	Output is correct
37	Correct	156 ms	12600 KB	Output is correct
38	Correct	158 ms	12416 KB	Output is correct
39	Correct	172 ms	12568 KB	Output is correct
40	Correct	255 ms	13892 KB	Output is correct
41	Partially correct	429 ms	16208 KB	Partially correct