oj.uz

Submission #101458

# Submission time Handle Problem Language Result Execution time Memory
101458 2019-03-19T02:38:59 Z dantoh000 007 (CEOI14_007) C++14
0 / 100
 505 ms 34808 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--;
    adjlist[serve1].push_back(serve2);
    adjlist[serve2].push_back(serve1);
    for (int i = 0; i < e; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if ((a == serve1 && b == serve2) || (a==serve2 && b == serve1)) continue;
        a--; b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    dfs(s0);
    //printf("%d %d %d\n",sn,serve1,lca(sn,serve1));
    if (lca(sn,serve1) == s0){
        printf("%d",d[sn]);
    }
    else{
        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:58: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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Partially correct 6 ms 5120 KB Partially correct
3 Incorrect 6 ms 5120 KB Output isn't correct
4 Incorrect 7 ms 5120 KB Output isn't correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Incorrect 6 ms 5120 KB Output isn't correct
7 Incorrect 8 ms 5248 KB Output isn't correct
8 Incorrect 6 ms 5092 KB Output isn't correct
9 Partially correct 7 ms 5248 KB Partially correct
10 Correct 7 ms 5092 KB Output is correct
11 Incorrect 6 ms 5120 KB Output isn't correct
12 Incorrect 8 ms 5120 KB Output isn't correct
13 Incorrect 8 ms 5248 KB Output isn't correct
14 Incorrect 9 ms 5248 KB Output isn't correct
15 Incorrect 8 ms 5120 KB Output isn't correct
16 Correct 7 ms 5248 KB Output is correct
17 Incorrect 7 ms 5248 KB Output isn't correct
18 Incorrect 7 ms 5248 KB Output isn't correct
19 Incorrect 7 ms 5248 KB Output isn't correct
20 Incorrect 7 ms 5248 KB Output isn't correct
21 Correct 7 ms 5248 KB Output is correct
22 Incorrect 7 ms 5248 KB Output isn't correct
23 Incorrect 7 ms 5248 KB Output isn't correct
24 Correct 7 ms 5248 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 10204 KB Output isn't correct
2 Incorrect 78 ms 13048 KB Output isn't correct
3 Incorrect 44 ms 10616 KB Output isn't correct
4 Incorrect 71 ms 13304 KB Output isn't correct
5 Correct 46 ms 10232 KB Output is correct
6 Correct 50 ms 11384 KB Output is correct
7 Incorrect 69 ms 12920 KB Output isn't correct
8 Incorrect 54 ms 11768 KB Output isn't correct
9 Incorrect 84 ms 12408 KB Output isn't correct
10 Incorrect 207 ms 17784 KB Output isn't correct
11 Incorrect 117 ms 16504 KB Output isn't correct
12 Incorrect 153 ms 19012 KB Output isn't correct
13 Incorrect 136 ms 17272 KB Output isn't correct
14 Correct 107 ms 15608 KB Output is correct
15 Incorrect 169 ms 19928 KB Output isn't correct
16 Correct 192 ms 20984 KB Output is correct
17 Incorrect 162 ms 22264 KB Output isn't correct
18 Incorrect 144 ms 19960 KB Output isn't correct
19 Incorrect 223 ms 21472 KB Output isn't correct
20 Incorrect 334 ms 24884 KB Output isn't correct
21 Incorrect 241 ms 26484 KB Output isn't correct
22 Incorrect 203 ms 23088 KB Output isn't correct
23 Partially correct 255 ms 26872 KB Partially correct
24 Incorrect 239 ms 25976 KB Output isn't correct
25 Incorrect 222 ms 23800 KB Output isn't correct
26 Partially correct 202 ms 23928 KB Partially correct
27 Incorrect 254 ms 29944 KB Output isn't correct
28 Incorrect 241 ms 26836 KB Output isn't correct
29 Incorrect 276 ms 25848 KB Output isn't correct
30 Incorrect 342 ms 26872 KB Output isn't correct
31 Incorrect 324 ms 29944 KB Output isn't correct
32 Incorrect 237 ms 25028 KB Output isn't correct
33 Partially correct 223 ms 27000 KB Partially correct
34 Incorrect 247 ms 26828 KB Output isn't correct
35 Incorrect 283 ms 26504 KB Output isn't correct
36 Correct 309 ms 27784 KB Output is correct
37 Correct 290 ms 30924 KB Output is correct
38 Incorrect 311 ms 34808 KB Output isn't correct
39 Incorrect 296 ms 30840 KB Output isn't correct
40 Correct 402 ms 32016 KB Output is correct
41 Incorrect 505 ms 33632 KB Output isn't correct