oj.uz

Submission #117063

# Submission time Handle Problem Language Result Execution time Memory
117063 2019-06-14T14:43:41 Z JohnTitor 007 (CEOI14_007) C++11
30 / 100
 243 ms 17400 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "007"
int n, m;
int s, d, a, b;
int a1, a2, b1, b2, w1, w2;
int fa[200001];
bool donea[200001];
int fb[200001];
bool doneb[200001];
vector <int> g[200001];
queue <int> q;
void bfs(int s, int *f, bool *done){
    FOR(i, 1, n) done[i]=0;
    f[s]=0;
    done[s]=1;
    q.push(s);
    while(!q.empty()){
        s=q.front();
        q.pop();
        for(int v: g[s]) if(!done[v]){
            done[v]=1;
            f[v]=f[s]+1;
            q.push(v);
        }
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(m);
    read(s);
    read(d);
    read(a);
    read(b);
    {
        int u, v;
        FOR(i, 1, m){
            read(u);
            read(v);
            g[u].pb(v);
            g[v].pb(u);
        }
    }
    bfs(a, fa, donea);
    bfs(b, fb, doneb);
    a1=fa[s];
    a2=fa[d];
    b1=fb[s];
    b2=fb[d];
    w1=a2-a1;
    w2=b2-b1;
    if(w1<0||w2<0){
        puts("-1");
        return 0;
    }
    else if(w1!=w2){
        writeln(min(w1, w2));
    }
    else{
        writeln(w1-1);
    }
}

Subtask #1
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 7216 KB Partially correct
2 Correct 27 ms 8184 KB Output is correct
3 Partially correct 23 ms 7316 KB Partially correct
4 Correct 28 ms 8332 KB Output is correct
5 Correct 21 ms 7168 KB Output is correct
6 Correct 23 ms 7424 KB Output is correct
7 Partially correct 27 ms 7672 KB Partially correct
8 Partially correct 31 ms 7544 KB Partially correct
9 Correct 39 ms 8184 KB Output is correct
10 Partially correct 114 ms 12588 KB Partially correct
11 Correct 57 ms 9436 KB Output is correct
12 Partially correct 62 ms 10460 KB Partially correct
13 Correct 52 ms 9720 KB Output is correct
14 Correct 42 ms 9080 KB Output is correct
15 Partially correct 66 ms 10488 KB Partially correct
16 Correct 70 ms 10780 KB Output is correct
17 Partially correct 53 ms 10232 KB Partially correct
18 Correct 60 ms 10360 KB Output is correct
19 Partially correct 91 ms 11512 KB Partially correct
20 Correct 163 ms 14200 KB Output is correct
21 Correct 93 ms 12560 KB Output is correct
22 Partially correct 90 ms 11612 KB Partially correct
23 Partially correct 90 ms 12280 KB Partially correct
24 Partially correct 85 ms 12280 KB Partially correct
25 Correct 88 ms 11896 KB Output is correct
26 Partially correct 82 ms 11608 KB Partially correct
27 Partially correct 127 ms 12456 KB Partially correct
28 Partially correct 127 ms 12408 KB Partially correct
29 Partially correct 163 ms 12920 KB Partially correct
30 Correct 184 ms 15100 KB Output is correct
31 Correct 137 ms 13392 KB Output is correct
32 Partially correct 111 ms 12280 KB Partially correct
33 Partially correct 109 ms 12568 KB Partially correct
34 Correct 144 ms 12880 KB Output is correct
35 Correct 106 ms 12664 KB Output is correct
36 Correct 101 ms 12892 KB Output is correct
37 Correct 145 ms 13756 KB Output is correct
38 Partially correct 147 ms 13688 KB Partially correct
39 Partially correct 181 ms 13600 KB Partially correct
40 Correct 186 ms 15096 KB Output is correct
41 Partially correct 243 ms 17400 KB Partially correct