oj.uz

Submission #349850

# Submission time Handle Problem Language Result Execution time Memory
349850 2021-01-18T14:10:57 Z doowey Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1119 ms 112360 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 100;
vector<int> T[N];
vector<pii> lis[N];

int dp[N];
int up[N];
int pp[N];

int trap;
int mouse;

void dfs(int u, int par){
    int deg = 0;
    for(auto x : T[u]) if(x != par) deg ++ ;
    for(auto x : T[u]){
        if(x==par) continue;
        pp[x]=u;
        up[x] += up[u] + (par != -1) * (deg - 1);
        dfs(x,u);
        lis[u].push_back(mp(dp[x],x));
    }
    sort(lis[u].begin(), lis[u].end());
    int mx = 0;
    if(lis[u].size() >= 2)
        mx = lis[u][lis[u].size() - 2].fi;
    dp[u]=mx+lis[u].size();
    reverse(lis[u].begin(), lis[u].end());
}

bool can(int mid){
    int cur = mouse;
    int pv = -1;
    int can = 1;
    int cnt = 0;
    while(cur != trap){
        cnt=0;
        for(int q = (int)lis[cur].size() - 1; q >= 0; q -- ){
            if(lis[cur][q].se == pv) continue;
            cnt ++ ;
        }
        for(auto x : lis[cur]){
            if(x.se == pv) continue;
            if(x.fi + up[cur] + cnt > mid){
                if(can==0)return false;
                can--;
            }
        }
        pv=cur;
        cur=pp[cur];
        can++;
    }
    return true;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    cin >> trap >> mouse;
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(trap,-1);
    int lf = 0, rf = (int)n * 2;
    int mid;
    while(lf < rf){
        mid = (lf + rf) / 2;
        if(can(mid)){
            rf=mid;
        }
        else{
            lf=mid+1;
        }
    }
    cout << lf << "\n";
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 108268 KB Output is correct
2 Correct 385 ms 101644 KB Output is correct
3 Correct 1078 ms 112076 KB Output is correct
4 Correct 526 ms 80520 KB Output is correct
5 Correct 1085 ms 112360 KB Output is correct
6 Correct 1119 ms 112236 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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