oj.uz

Submission #143514

# Submission time Handle Problem Language Result Execution time Memory
143514 2019-08-14T12:30:17 Z popovicirobert Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1097 ms 75996 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



/*const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int MAXN = (int) 1e6;

vector <int> g[MAXN + 1];
int father[MAXN + 1], lvl[MAXN + 1];

void dfs(int nod, int par) {
    father[nod] = par;
    lvl[nod] = lvl[par] + 1;
    for(auto it : g[nod]) {
        if(it != par) {
            dfs(it, nod);
        }
    }
}

int dp[MAXN + 1];
bool vis[MAXN + 1];

inline void combine(pair <int, int> &mx, int cur) {
    if(mx.first < cur) {
        mx.second = mx.first;
        mx.first = cur;
    }
    else if(mx.second < cur) {
        mx.second = cur;
    }
}

void go(int nod, int par, int sum) {
    int sz = (int) g[nod].size() - 1;
    pair <int, int> mx = {0, 0};
    for(auto it : g[nod]) {
        if(it != par) {
            go(it, nod, sum + sz - vis[nod]);
            combine(mx, dp[it]);
        }
    }
    if(sz > 1) {
        dp[nod] = mx.second;
    }
    else {
         dp[nod] = sz - vis[nod] + sum;
    }
}

int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n, t, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> t >> m;

    if(m == t) {
        cout << 0;
        return 0;
    }

    for(i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(t, 0);

    int nod = m, dst = 1;
    vector < pair <int, int> > nodes; nodes.push_back({m, 0});

    while(father[nod] != t) {
        dst++;
        for(auto it : g[father[nod]]) {
            if(it != nod && lvl[it] == lvl[nod]) {
                nodes.push_back({it, dst});
            }
        }
        nod = father[nod];
        vis[nod] = 1;
    }
    go(nod, t, 0);

    auto check = [&](int X) -> bool {
        int cnt = 0;
        for(auto it : nodes) {
            if(dp[it.first] + cnt > X) {
                cnt++;
            }
            if(cnt > it.second) {
                return 0;
            }
        }
        return cnt <= X;
    };

    int res = -1;
    for(int step = 1 << 20; step; step >>= 1) {
        if(check(res + step) == 0) {
            res += step;
        }
    }

    cout << res + 1;

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 30 ms 23800 KB Output is correct
6 Correct 24 ms 23896 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23832 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 75996 KB Output is correct
2 Correct 420 ms 69684 KB Output is correct
3 Correct 1097 ms 74852 KB Output is correct
4 Correct 534 ms 52320 KB Output is correct
5 Correct 1062 ms 74908 KB Output is correct
6 Correct 1063 ms 74924 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 30 ms 23800 KB Output is correct
6 Correct 24 ms 23896 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23832 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Incorrect 23 ms 23896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23800 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 30 ms 23800 KB Output is correct
6 Correct 24 ms 23896 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23832 KB Output is correct
9 Correct 24 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 451 ms 75996 KB Output is correct
12 Correct 420 ms 69684 KB Output is correct
13 Correct 1097 ms 74852 KB Output is correct
14 Correct 534 ms 52320 KB Output is correct
15 Correct 1062 ms 74908 KB Output is correct
16 Correct 1063 ms 74924 KB Output is correct
17 Incorrect 23 ms 23896 KB Output isn't correct
18 Halted 0 ms 0 KB -