oj.uz

답안 #65044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65044 2018-08-06T13:39:20 Z bazsi700 007 (CEOI14_007) C++14
9 / 100
 477 ms 17536 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,s,d,a,b;
    cin >> n >> m >> s >> d >> a >> b;
    vector<vector<int> > graph(n+1,vector<int>());
    for(int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    vector<bool> wass(n+1,false);
    vector<int> dists(n+1,0);
    vector<bool> wasd(n+1,false);
    vector<int> distd(n+1,0);
    vector<bool> wasa(n+1,false);
    vector<int> dista(n+1,0);
    vector<bool> wasb(n+1,false);
    vector<int> distb(n+1,0);
    wass[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wass[u]) {
                wass[u] = true;
                q.push(u);
                dists[u] = dists[v]+1;
            }
        }
    }
    wasd[d] = true;
    q.push(d);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasd[u]) {
                wasd[u] = true;
                q.push(u);
                distd[u] = distd[v]+1;
            }
        }
    }
    wasa[a] = true;
    q.push(a);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasa[u]) {
                wasa[u] = true;
                q.push(u);
                dista[u] = dista[v]+1;
            }
        }
    }
    wasb[b] = true;
    q.push(b);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasb[u]) {
                wasb[u] = true;
                q.push(u);
                distb[u] = distb[v]+1;
            }
        }
    }
    if(dists[a] == dists[b] && distd[a] == distd[b]) {
        int mxdistd = -1;
        int mxdists = -1;
        for(int i = 1; i <= n; i++) {
            if(dista[i] == distb[i]) {
                if(dista[i]+distd[i] == distd[a]) {
                    mxdistd = max(mxdistd,dista[i]);
                }
                if(dista[i]+dists[i] == dists[a]) {
                    mxdists = max(mxdists,dista[i]);
                }
            }
        }
        if(mxdists >= mxdistd-100) {
            cout << max(min(distd[a]-dists[a],distd[b]-dists[b])-1,-1);
        } else {
            cout << max(min(distd[a]-dists[a],distd[b]-dists[b]),-1);
        }
    } else {
        cout << max(min(distd[a]-dists[a],distd[b]-dists[b]),-1);
    }
    return 0;
}

Subtask #1
9.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 5 ms 488 KB Output is correct
3 Partially correct 3 ms 552 KB Partially correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Partially correct 3 ms 552 KB Partially correct
7 Partially correct 3 ms 568 KB Partially correct
8 Correct 3 ms 696 KB Output is correct
9 Partially correct 3 ms 696 KB Partially correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Partially correct 3 ms 696 KB Partially correct
14 Correct 2 ms 696 KB Output is correct
15 Partially correct 3 ms 696 KB Partially correct
16 Correct 3 ms 696 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 3 ms 724 KB Output is correct
19 Partially correct 3 ms 724 KB Partially correct
20 Partially correct 3 ms 724 KB Partially correct
21 Correct 4 ms 724 KB Output is correct
22 Partially correct 3 ms 724 KB Partially correct
23 Partially correct 4 ms 724 KB Partially correct
24 Correct 4 ms 724 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 46 ms 3452 KB Partially correct
2 Incorrect 52 ms 4860 KB Output isn't correct
3 Partially correct 60 ms 4860 KB Partially correct
4 Incorrect 52 ms 5116 KB Output isn't correct
5 Correct 45 ms 5116 KB Output is correct
6 Correct 45 ms 5116 KB Output is correct
7 Partially correct 49 ms 5116 KB Partially correct
8 Partially correct 56 ms 5116 KB Partially correct
9 Correct 58 ms 5116 KB Output is correct
10 Partially correct 218 ms 9344 KB Partially correct
11 Incorrect 69 ms 9344 KB Output isn't correct
12 Partially correct 108 ms 9344 KB Partially correct
13 Correct 116 ms 9344 KB Output is correct
14 Correct 91 ms 9344 KB Output is correct
15 Correct 139 ms 9344 KB Output is correct
16 Correct 150 ms 9344 KB Output is correct
17 Correct 131 ms 9344 KB Output is correct
18 Correct 134 ms 9344 KB Output is correct
19 Partially correct 193 ms 9560 KB Partially correct
20 Correct 362 ms 12580 KB Output is correct
21 Incorrect 208 ms 12580 KB Output isn't correct
22 Partially correct 169 ms 12580 KB Partially correct
23 Correct 151 ms 12580 KB Output is correct
24 Correct 154 ms 12580 KB Output is correct
25 Incorrect 158 ms 12580 KB Output isn't correct
26 Correct 137 ms 12580 KB Output is correct
27 Correct 218 ms 12580 KB Output is correct
28 Partially correct 233 ms 12580 KB Partially correct
29 Partially correct 296 ms 12580 KB Partially correct
30 Correct 316 ms 13768 KB Output is correct
31 Incorrect 189 ms 13768 KB Output isn't correct
32 Partially correct 211 ms 13768 KB Partially correct
33 Correct 184 ms 13768 KB Output is correct
34 Correct 198 ms 13768 KB Output is correct
35 Incorrect 202 ms 13768 KB Output isn't correct
36 Incorrect 217 ms 13768 KB Output isn't correct
37 Correct 269 ms 14356 KB Output is correct
38 Partially correct 213 ms 14356 KB Partially correct
39 Partially correct 286 ms 14356 KB Partially correct
40 Incorrect 395 ms 15364 KB Output isn't correct
41 Partially correct 477 ms 17536 KB Partially correct