oj.uz

답안 #391849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391849 2021-04-20T03:44:08 Z cheissmart 007 (CEOI14_007) C++14
30 / 100
 296 ms 17896 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") ->" << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int da[N], db[N], ds[N], dd[N];
vi G[N];

void BFS(int s, int* d) {
    d[s] = 0;
    queue<int> q({s});
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int v:G[u]) if(d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

    memset(da, -1, sizeof da);
    memset(db, -1, sizeof db);
    memset(ds, -1, sizeof ds);
    memset(dd, -1, sizeof dd);

    int n, m;
    cin >> n >> m;
    int s, d, a, b;
    cin >> s >> d >> a >> b;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].PB(v), G[v].PB(u);
    }
    BFS(a, da), BFS(b, db), BFS(s, ds), BFS(d, dd);
    if(da[s] != db[s]) {
        int can = min(da[d] - da[s], db[d] - db[s]);
        if(can < 0) can = -1;
        cout << can << '\n';
    } else {
        int need = INF;
        for(int i = 1; i <= n; i++) {
            if(da[i] < da[s] || db[i] < db[s] || (da[i] == da[s] && db[i] == db[s])) {
                need = min(need, dd[i]);
            }
        }
        cout << need - 1 << '\n';
    }

}

Subtask #1
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 26 ms 9340 KB Partially correct
2 Correct 33 ms 10000 KB Output is correct
3 Partially correct 28 ms 9412 KB Partially correct
4 Correct 35 ms 10040 KB Output is correct
5 Correct 27 ms 9276 KB Output is correct
6 Correct 26 ms 9452 KB Output is correct
7 Correct 32 ms 9684 KB Output is correct
8 Correct 30 ms 9548 KB Output is correct
9 Correct 45 ms 10092 KB Output is correct
10 Partially correct 150 ms 14296 KB Partially correct
11 Correct 58 ms 10948 KB Output is correct
12 Partially correct 81 ms 11588 KB Partially correct
13 Correct 67 ms 11180 KB Output is correct
14 Correct 50 ms 10644 KB Output is correct
15 Partially correct 78 ms 11704 KB Partially correct
16 Correct 79 ms 11852 KB Output is correct
17 Correct 69 ms 11428 KB Output is correct
18 Correct 75 ms 11460 KB Output is correct
19 Partially correct 108 ms 12628 KB Partially correct
20 Correct 208 ms 15644 KB Output is correct
21 Correct 105 ms 13096 KB Output is correct
22 Partially correct 103 ms 12472 KB Partially correct
23 Correct 105 ms 13064 KB Output is correct
24 Partially correct 106 ms 12976 KB Partially correct
25 Correct 105 ms 12740 KB Output is correct
26 Correct 96 ms 12480 KB Output is correct
27 Correct 116 ms 13056 KB Output is correct
28 Correct 129 ms 13128 KB Output is correct
29 Partially correct 152 ms 13880 KB Partially correct
30 Correct 216 ms 15968 KB Output is correct
31 Correct 132 ms 13892 KB Output is correct
32 Partially correct 128 ms 13012 KB Partially correct
33 Correct 128 ms 13292 KB Output is correct
34 Correct 143 ms 13508 KB Output is correct
35 Correct 112 ms 13280 KB Output is correct
36 Correct 113 ms 13508 KB Output is correct
37 Correct 158 ms 14148 KB Output is correct
38 Correct 152 ms 14064 KB Output is correct
39 Correct 169 ms 14088 KB Output is correct
40 Correct 205 ms 15716 KB Output is correct
41 Partially correct 296 ms 17896 KB Partially correct