oj.uz

답안 #101454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101454 2019-03-19T02:32:19 Z dantoh000 007 (CEOI14_007) C++14
0 / 100
 452 ms 61768 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;
        //printf("%d -> %d\n",x,v);
        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);
    s0--, sn--, serve1--, serve2--;
    for (int i = 0; i < e; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        a--; b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    dfs(serve1);
    //printf("%d %d\nvs\n%d %d\n",dist(s0,serve1),dist(s0,serve2),dist(sn,serve1),dist(sn,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

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

Compilation message

007.cpp: In function 'int lca(int, int)':
007.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:50: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:52: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:56: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 Incorrect 8 ms 5248 KB Output isn't correct
2 Incorrect 7 ms 5120 KB Output isn't correct
3 Incorrect 6 ms 5120 KB Output isn't correct
4 Incorrect 7 ms 5120 KB Output isn't correct
5 Partially correct 7 ms 5120 KB Partially correct
6 Runtime error 14 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Partially correct 6 ms 5120 KB Partially correct
9 Incorrect 7 ms 5120 KB Output isn't correct
10 Incorrect 7 ms 5120 KB Output isn't correct
11 Incorrect 7 ms 5120 KB Output isn't correct
12 Incorrect 7 ms 5248 KB Output isn't correct
13 Incorrect 7 ms 5220 KB Output isn't correct
14 Runtime error 16 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 17 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 7 ms 5248 KB Output isn't correct
17 Incorrect 8 ms 5220 KB Output isn't correct
18 Incorrect 8 ms 5248 KB Output isn't correct
19 Incorrect 7 ms 5248 KB Output isn't correct
20 Incorrect 8 ms 5248 KB Output isn't correct
21 Incorrect 8 ms 5248 KB Output isn't correct
22 Incorrect 9 ms 5248 KB Output isn't correct
23 Incorrect 8 ms 5248 KB Output isn't correct
24 Incorrect 7 ms 5296 KB Output isn't correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 61 ms 10204 KB Output isn't correct
2 Incorrect 82 ms 13176 KB Output isn't correct
3 Incorrect 54 ms 10616 KB Output isn't correct
4 Incorrect 102 ms 13176 KB Output isn't correct
5 Incorrect 49 ms 10104 KB Output isn't correct
6 Incorrect 49 ms 11640 KB Output isn't correct
7 Runtime error 68 ms 25336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 66 ms 11896 KB Output isn't correct
9 Incorrect 88 ms 12536 KB Output isn't correct
10 Incorrect 214 ms 17784 KB Output isn't correct
11 Incorrect 128 ms 16376 KB Output isn't correct
12 Incorrect 232 ms 19320 KB Output isn't correct
13 Incorrect 145 ms 17144 KB Output isn't correct
14 Incorrect 126 ms 15480 KB Output isn't correct
15 Incorrect 200 ms 19796 KB Output isn't correct
16 Incorrect 185 ms 20984 KB Output isn't correct
17 Runtime error 222 ms 44156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 199 ms 39800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Partially correct 219 ms 21624 KB Partially correct
20 Correct 330 ms 24724 KB Output is correct
21 Incorrect 287 ms 26104 KB Output isn't correct
22 Incorrect 206 ms 22952 KB Output isn't correct
23 Incorrect 253 ms 26616 KB Output isn't correct
24 Incorrect 258 ms 25776 KB Output isn't correct
25 Incorrect 229 ms 23888 KB Output isn't correct
26 Incorrect 227 ms 24156 KB Output isn't correct
27 Runtime error 324 ms 58980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 280 ms 53368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Partially correct 310 ms 25680 KB Partially correct
30 Correct 439 ms 26744 KB Output is correct
31 Incorrect 286 ms 29048 KB Output isn't correct
32 Incorrect 262 ms 25132 KB Output isn't correct
33 Incorrect 268 ms 27256 KB Output isn't correct
34 Incorrect 268 ms 26616 KB Output isn't correct
35 Incorrect 248 ms 27376 KB Output isn't correct
36 Incorrect 291 ms 28128 KB Output isn't correct
37 Incorrect 306 ms 30912 KB Output isn't correct
38 Incorrect 355 ms 34636 KB Output isn't correct
39 Runtime error 364 ms 61768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Incorrect 446 ms 31992 KB Output isn't correct
41 Partially correct 452 ms 33636 KB Partially correct