oj.uz

Submission #207622

# Submission time Handle Problem Language Result Execution time Memory
207622 2020-03-08T07:07:22 Z PeppaPig Torrent (COI16_torrent) C++14
100 / 100
 516 ms 29424 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5+5;

int n, a, b;
int E[N], par[N], block[N], dp[N];
vector<int> g[N];

void dfs(int u, int p) {
    par[u] = p;
    for(int v : g[u]) if(v != p)
        dfs(u ^ E[v], v);
}

int process(int u, int p) {
    dp[u] = 0;
    vector<int> child;
    for(int v : g[u]) if(v != p && !block[v])
        child.emplace_back(process(E[v] ^ u, v));
    sort(child.begin(), child.end(), greater<int>());
    for(int i = 0; i < child.size(); i++)
        dp[u] = max(dp[u], 1 + i + child[i]);
    return dp[u];
}

int main() {
    scanf("%d %d %d", &n, &a, &b);
    for(int i = 1, a, b; i < n; i++) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(i), g[b].emplace_back(i);
        E[i] = a ^ b;
    }
    dfs(b, 0);
    vector<int> vec;
    int now = a;
    while(now != b) {
        vec.emplace_back(par[now]);
        now ^= E[par[now]];
    }
    int l = 0, r = vec.size() - 1;
    int ans = 1e9;
    while(l <= r) {
        int mid = (l + r) >> 1;

        block[vec[mid]] = 1;
        int t_a = process(a, 0), t_b = process(b, 0);
        block[vec[mid]] = 0;

        ans = min(ans, max(t_a, t_b));
        if(t_a == t_b) break;
        else if(t_a < t_b) l = mid + 1;
        else r = mid - 1;
    }
    printf("%d\n", ans);

    return 0;
}

Compilation message

torrent.cpp: In function 'int process(int, int)':
torrent.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < child.size(); i++)
                    ~~^~~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:31: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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 26872 KB Output is correct
2 Correct 492 ms 27864 KB Output is correct
3 Correct 494 ms 29076 KB Output is correct
4 Correct 516 ms 28596 KB Output is correct
5 Correct 479 ms 26232 KB Output is correct
6 Correct 473 ms 26692 KB Output is correct
7 Correct 457 ms 29424 KB Output is correct