oj.uz

답안 #101450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101450 2019-03-19T02:25:55 Z dantoh000 007 (CEOI14_007) C++14
0 / 100
 263 ms 30140 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200001;
const int logn = 18;
int p[logn+1][maxn], h[maxn];
int H[maxn];
int d[maxn];
vector<int> adjlist[maxn];
bitset<maxn> vis;
void dfs(int x){
    if (vis[x]) return;
    vis[x] = 1;
    for (int k = 0; k < logn; k++){
        if (p[k][x] == -1) break;
        p[k+1][x] = p[k][p[k][x]];
    }
    for (auto v : adjlist[x]){
        if (vis[v]) continue;
        p[0][v] = x;
        d[v] = d[x]+1;
        h[v] = h[x]+1;
        dfs(v);
    }
}
int lca(int a, int b){
    if (h[a] > h[b]) swap(a,b);
    for (int k = 0, d= h[b] - h[a]; k < logn; k++){
        if (d & (1<<k)) b = p[k][b];
    }
    if (a==b) return a;
    assert(h[a] == h[b]);
    for (int k = logn-1; k >=0; --k){
        if (p[k][a] != p[k][b])
            a = p[k][a], b = p[k][b];
        assert(p[0][a] == p[0][b]);
        return p[0][a];
    }
}
int anc(int x, int d){
    for (int k = 0; k <= logn && x != -1; k++){
        if (d & (1<<k)) x = p[k][x];
    }
    return x;
}
int dist(int a, int b){
    return d[a] + d[b] - 2*d[lca(a,b)];
}
int main(){
    int n,e; scanf("%d%d",&n,&e);
    int s0, sn, serve1, serve2;
    scanf("%d%d%d%d",&s0,&sn,&serve1,&serve2);
    for (int i = 0; i < e; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        adjlist[a].push_back(b);
    }
    dfs(s0);
    //printf("%d %d\n",dist(s0,serve1),dist(s0,serve2));
    int dist0 = max(dist(s0,serve1),dist(s0,serve2));
    int distn = min(dist(sn,serve1),dist(sn,serve2));
    //printf("%d %d\n",dist0,distn);
    if (dist0 > distn){
        printf("-1");
    }
    else printf("%d",distn-dist0);


}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

Compilation message

007.cpp: In function 'int lca(int, int)':
007.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:49:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n,e; scanf("%d%d",&n,&e);
              ~~~~~^~~~~~~~~~~~~~
007.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&s0,&sn,&serve1,&serve2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Incorrect 6 ms 5120 KB Output isn't correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 9 ms 5120 KB Output is correct
6 Incorrect 7 ms 5120 KB Output isn't correct
7 Incorrect 8 ms 5120 KB Output isn't correct
8 Correct 8 ms 5120 KB Output is correct
9 Incorrect 8 ms 5148 KB Output isn't correct
10 Incorrect 8 ms 5120 KB Output isn't correct
11 Partially correct 8 ms 5120 KB Partially correct
12 Incorrect 8 ms 5248 KB Output isn't correct
13 Incorrect 8 ms 5248 KB Output isn't correct
14 Incorrect 7 ms 5120 KB Output isn't correct
15 Incorrect 7 ms 5120 KB Output isn't correct
16 Incorrect 8 ms 5120 KB Output isn't correct
17 Incorrect 7 ms 5120 KB Output isn't correct
18 Incorrect 9 ms 5248 KB Output isn't correct
19 Incorrect 8 ms 5120 KB Output isn't correct
20 Incorrect 7 ms 5248 KB Output isn't correct
21 Incorrect 8 ms 5120 KB Output isn't correct
22 Incorrect 9 ms 5120 KB Output isn't correct
23 Incorrect 8 ms 5260 KB Output isn't correct
24 Correct 7 ms 5248 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 6648 KB Output isn't correct
2 Incorrect 41 ms 7288 KB Output isn't correct
3 Incorrect 29 ms 6904 KB Output isn't correct
4 Incorrect 48 ms 7416 KB Output isn't correct
5 Incorrect 32 ms 6776 KB Output isn't correct
6 Incorrect 33 ms 6568 KB Output isn't correct
7 Incorrect 41 ms 6804 KB Output isn't correct
8 Incorrect 41 ms 7260 KB Output isn't correct
9 Incorrect 55 ms 7580 KB Output isn't correct
10 Incorrect 187 ms 14072 KB Output isn't correct
11 Incorrect 54 ms 8440 KB Output isn't correct
12 Incorrect 67 ms 9336 KB Output isn't correct
13 Incorrect 53 ms 8584 KB Output isn't correct
14 Incorrect 53 ms 8056 KB Output isn't correct
15 Incorrect 79 ms 9336 KB Output isn't correct
16 Incorrect 88 ms 9464 KB Output isn't correct
17 Incorrect 67 ms 9212 KB Output isn't correct
18 Incorrect 62 ms 9344 KB Output isn't correct
19 Incorrect 190 ms 20344 KB Output isn't correct
20 Incorrect 257 ms 26528 KB Output isn't correct
21 Incorrect 77 ms 10872 KB Output isn't correct
22 Incorrect 78 ms 10104 KB Output isn't correct
23 Incorrect 88 ms 10744 KB Output isn't correct
24 Incorrect 113 ms 11016 KB Output isn't correct
25 Incorrect 82 ms 10548 KB Output isn't correct
26 Incorrect 93 ms 10076 KB Output isn't correct
27 Incorrect 115 ms 10908 KB Output isn't correct
28 Incorrect 115 ms 11100 KB Output isn't correct
29 Incorrect 191 ms 24156 KB Output isn't correct
30 Incorrect 193 ms 15992 KB Output isn't correct
31 Incorrect 118 ms 11896 KB Output isn't correct
32 Incorrect 130 ms 10916 KB Output isn't correct
33 Incorrect 129 ms 11172 KB Output isn't correct
34 Incorrect 123 ms 11512 KB Output isn't correct
35 Incorrect 83 ms 11128 KB Output isn't correct
36 Incorrect 96 ms 11512 KB Output isn't correct
37 Incorrect 101 ms 12152 KB Output isn't correct
38 Incorrect 104 ms 12336 KB Output isn't correct
39 Incorrect 91 ms 12024 KB Output isn't correct
40 Incorrect 227 ms 30140 KB Output isn't correct
41 Incorrect 263 ms 18332 KB Output isn't correct