oj.uz

Submission #143529

# Submission time Handle Problem Language Result Execution time Memory
143529 2019-08-14T13:58:42 Z popovicirobert Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1055 ms 68188 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, num = 0;
        for(i = 0; i < nodes.size(); i++) {
            int last = (i == 0 ? -1 : nodes[i - 1].second);
            if(last != nodes[i].second) {
                num = 0;
            }
            if(dp[nodes[i].first] + cnt - num > X) {
                cnt++, num++;
            }
            if(cnt > nodes[i].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;
}

Compilation message

mousetrap.cpp: In lambda function:
mousetrap.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i = 0; i < nodes.size(); i++) {
                    ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23804 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 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 435 ms 66900 KB Output is correct
2 Correct 409 ms 62540 KB Output is correct
3 Correct 1055 ms 68188 KB Output is correct
4 Correct 507 ms 46080 KB Output is correct
5 Correct 1034 ms 68124 KB Output is correct
6 Correct 1048 ms 68088 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23804 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 435 ms 66900 KB Output is correct
12 Correct 409 ms 62540 KB Output is correct
13 Correct 1055 ms 68188 KB Output is correct
14 Correct 507 ms 46080 KB Output is correct
15 Correct 1034 ms 68124 KB Output is correct
16 Correct 1048 ms 68088 KB Output is correct
17 Incorrect 23 ms 23800 KB Output isn't correct
18 Halted 0 ms 0 KB -