oj.uz

Submission #250335

# Submission time Handle Problem Language Result Execution time Memory
250335 2020-07-17T12:56:30 Z Sorting Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 631 ms 524292 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e6 + 3;

int n, trap, mouse;
int a[k_N], d[k_N], dp[k_N];
vector<int> adj[k_N];
vector<pair<int, int>> v;

void dfs(int u, int p){
    pair<int, int> ret;
    for(int to: adj[u]){
        if(to == p) continue;
        if(p != -1)
            dp[to] += dp[u] + adj[u].size() - 2;

        dfs(to, u);

        a[u] |= a[to];
        ret.second = max(dp[to], ret.second);
        if(ret.second > ret.first)
            swap(ret.first, ret.second);
    }

    if(adj[u].size() > 2)
        dp[u] = ret.second;
    dp[u] += adj[u].size() > 1;
}

void dfs2(int u, int p){
    if(u == trap)
        return;
    for(int to: adj[u]){
        if(to == p) continue;

        d[to] = d[u] + 1;
        dfs2(u, to);

        if(a[u] && !a[to])
            v.push_back({d[to], dp[to] + (u == mouse)});
    }
}

bool works(int x){
    int ret = 0;
    for(auto p: v){
        if(ret > p.first)
            return false;
        ret += (p.second + ret) > x;
    }
    return ret <= x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> trap >> mouse;

    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    a[mouse] = 1;
    d[mouse] = -1;

    dfs(trap, -1);
    dfs2(mouse, -1);

    sort(v.begin(), v.end());

    int l = 0, r = n;
    while(l != r){
        int mid = (l + r) >> 1;
        if(works(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << "\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 631 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -