oj.uz

Submission #117064

# Submission time Handle Problem Language Result Execution time Memory
117064 2019-06-14T14:46:49 Z JohnTitor 007 (CEOI14_007) C++11
100 / 100
 272 ms 17656 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 dp[200001];
bool done[200001];
int DP(int u){
    if(done[u]) return dp[u];
    done[u]=1;
    for(int v: g[u]) if(fa[v]<fa[u]&&fb[v]<fb[u]) dp[u]=max(dp[u], DP(v)+1);
    return dp[u];
}
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{
        int x=DP(s);
        int y=DP(d);
        if(x+w1>=y) writeln(w1);
        else writeln(w1-1);
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7032 KB Output is correct
2 Correct 31 ms 8056 KB Output is correct
3 Correct 26 ms 7132 KB Output is correct
4 Correct 33 ms 8056 KB Output is correct
5 Correct 22 ms 6912 KB Output is correct
6 Correct 24 ms 7040 KB Output is correct
7 Correct 31 ms 7288 KB Output is correct
8 Correct 34 ms 7348 KB Output is correct
9 Correct 40 ms 7928 KB Output is correct
10 Correct 123 ms 12176 KB Output is correct
11 Correct 51 ms 9336 KB Output is correct
12 Correct 57 ms 10360 KB Output is correct
13 Correct 47 ms 9624 KB Output is correct
14 Correct 39 ms 8568 KB Output is correct
15 Correct 59 ms 10616 KB Output is correct
16 Correct 55 ms 10136 KB Output is correct
17 Correct 59 ms 9596 KB Output is correct
18 Correct 59 ms 9976 KB Output is correct
19 Correct 94 ms 11512 KB Output is correct
20 Correct 162 ms 14240 KB Output is correct
21 Correct 93 ms 12880 KB Output is correct
22 Correct 86 ms 11480 KB Output is correct
23 Correct 110 ms 13032 KB Output is correct
24 Correct 122 ms 12620 KB Output is correct
25 Correct 73 ms 11952 KB Output is correct
26 Correct 87 ms 11768 KB Output is correct
27 Correct 101 ms 11844 KB Output is correct
28 Correct 129 ms 11964 KB Output is correct
29 Correct 146 ms 13048 KB Output is correct
30 Correct 206 ms 14968 KB Output is correct
31 Correct 154 ms 14072 KB Output is correct
32 Correct 144 ms 12388 KB Output is correct
33 Correct 99 ms 12792 KB Output is correct
34 Correct 146 ms 12996 KB Output is correct
35 Correct 111 ms 13176 KB Output is correct
36 Correct 105 ms 13532 KB Output is correct
37 Correct 134 ms 13208 KB Output is correct
38 Correct 114 ms 13012 KB Output is correct
39 Correct 151 ms 13052 KB Output is correct
40 Correct 181 ms 15556 KB Output is correct
41 Correct 272 ms 17656 KB Output is correct