oj.uz

답안 #391853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391853 2021-04-20T03:49:11 Z wiwiho 007 (CEOI14_007) C++14
30 / 100
 275 ms 16992 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

using pii = pair<int, int>;

ostream& operator<<(ostream& o, pii p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int n, m;
vector<vector<int>> g;

vector<int> getdis(int s){
    vector<int> dis(n + 1, -1);
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i : g[now]){
            if(dis[i] != -1) continue;
            dis[i] = dis[now] + 1;
            q.push(i);
        }
    }
    return dis;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    int s, d, a, b;
    cin >> s >> d >> a >> b;

    g.resize(n + 1);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    vector<int> ds = getdis(s);
    vector<int> dd = getdis(d);
    vector<int> da = getdis(a);
    vector<int> db = getdis(b);

    int tmp = min(dd[a], dd[b]);
    int ans = ds[a];
    for(int i = 1; i <= n; i++){
        if(da[i] <= 1 && db[i] <= 1){
            ans = min(ds[i], ans);
        }
    }
    ans = tmp - 1 - ans;
    ans = max(ans, -1);
    cout << ans << "\n";

    return 0;
}

Subtask #1
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 22 ms 3148 KB Partially correct
2 Correct 29 ms 4460 KB Output is correct
3 Partially correct 25 ms 3344 KB Partially correct
4 Correct 33 ms 4696 KB Output is correct
5 Correct 24 ms 3020 KB Output is correct
6 Correct 22 ms 3444 KB Output is correct
7 Partially correct 26 ms 3720 KB Partially correct
8 Partially correct 27 ms 3720 KB Partially correct
9 Correct 37 ms 4164 KB Output is correct
10 Partially correct 142 ms 8808 KB Partially correct
11 Correct 53 ms 6596 KB Output is correct
12 Partially correct 78 ms 8228 KB Partially correct
13 Correct 61 ms 7120 KB Output is correct
14 Correct 47 ms 6160 KB Output is correct
15 Partially correct 71 ms 8472 KB Partially correct
16 Correct 79 ms 8828 KB Output is correct
17 Partially correct 66 ms 7912 KB Partially correct
18 Correct 75 ms 8004 KB Output is correct
19 Partially correct 109 ms 9248 KB Partially correct
20 Correct 185 ms 12108 KB Output is correct
21 Correct 97 ms 11596 KB Output is correct
22 Partially correct 101 ms 10060 KB Partially correct
23 Partially correct 110 ms 11376 KB Partially correct
24 Partially correct 109 ms 11340 KB Partially correct
25 Correct 102 ms 10656 KB Output is correct
26 Partially correct 91 ms 10176 KB Partially correct
27 Partially correct 116 ms 11500 KB Partially correct
28 Partially correct 144 ms 11560 KB Partially correct
29 Partially correct 146 ms 11452 KB Partially correct
30 Correct 203 ms 13300 KB Output is correct
31 Correct 130 ms 13220 KB Output is correct
32 Partially correct 134 ms 11460 KB Partially correct
33 Partially correct 119 ms 11892 KB Partially correct
34 Correct 138 ms 12320 KB Output is correct
35 Correct 115 ms 12048 KB Output is correct
36 Correct 122 ms 12452 KB Output is correct
37 Correct 148 ms 14004 KB Output is correct
38 Partially correct 152 ms 13636 KB Partially correct
39 Partially correct 172 ms 13700 KB Partially correct
40 Correct 215 ms 15012 KB Output is correct
41 Partially correct 275 ms 16992 KB Partially correct