oj.uz

Submission #349857

# Submission time Handle Problem Language Result Execution time Memory
349857 2021-01-18T14:27:32 Z doowey Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1081 ms 260460 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 can = 1;
    int alr = 0;
    int pv = -1;
    int cnt;
    int need;
    while(cur != trap){
        cnt = 0;
        for(auto x : lis[cur]){
            if(x.se == pv) continue;
            cnt ++ ;
        }
        need = 0;
        for(auto x : lis[cur]){
            if(x.se == pv) continue;
            if(up[cur]+x.fi+cnt+alr > mid){
                need ++ ;
                if(can == 0){
                    return false;
                }
                can -- ;
            }
        }
        alr += need;
        pv=cur;
        cur = pp[cur];
        can++;
    }
    if(alr > mid) return false;
    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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 33 ms 47468 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 33 ms 47340 KB Output is correct
10 Correct 33 ms 47340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 106328 KB Output is correct
2 Correct 382 ms 100204 KB Output is correct
3 Correct 1069 ms 110236 KB Output is correct
4 Correct 511 ms 78828 KB Output is correct
5 Correct 1072 ms 110056 KB Output is correct
6 Correct 1061 ms 110444 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 33 ms 47468 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 33 ms 47340 KB Output is correct
10 Correct 33 ms 47340 KB Output is correct
11 Correct 33 ms 47340 KB Output is correct
12 Correct 33 ms 47340 KB Output is correct
13 Correct 32 ms 47428 KB Output is correct
14 Correct 33 ms 47596 KB Output is correct
15 Correct 34 ms 47468 KB Output is correct
16 Correct 33 ms 47340 KB Output is correct
17 Correct 32 ms 47340 KB Output is correct
18 Correct 33 ms 47340 KB Output is correct
19 Correct 33 ms 47340 KB Output is correct
20 Correct 33 ms 47468 KB Output is correct
21 Correct 33 ms 47468 KB Output is correct
22 Correct 32 ms 47340 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 33 ms 47340 KB Output is correct
4 Correct 33 ms 47340 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47340 KB Output is correct
7 Correct 33 ms 47468 KB Output is correct
8 Correct 32 ms 47340 KB Output is correct
9 Correct 33 ms 47340 KB Output is correct
10 Correct 33 ms 47340 KB Output is correct
11 Correct 416 ms 106328 KB Output is correct
12 Correct 382 ms 100204 KB Output is correct
13 Correct 1069 ms 110236 KB Output is correct
14 Correct 511 ms 78828 KB Output is correct
15 Correct 1072 ms 110056 KB Output is correct
16 Correct 1061 ms 110444 KB Output is correct
17 Correct 33 ms 47340 KB Output is correct
18 Correct 33 ms 47340 KB Output is correct
19 Correct 32 ms 47428 KB Output is correct
20 Correct 33 ms 47596 KB Output is correct
21 Correct 34 ms 47468 KB Output is correct
22 Correct 33 ms 47340 KB Output is correct
23 Correct 32 ms 47340 KB Output is correct
24 Correct 33 ms 47340 KB Output is correct
25 Correct 33 ms 47340 KB Output is correct
26 Correct 33 ms 47468 KB Output is correct
27 Correct 33 ms 47468 KB Output is correct
28 Correct 32 ms 47340 KB Output is correct
29 Correct 32 ms 47340 KB Output is correct
30 Correct 444 ms 119404 KB Output is correct
31 Correct 423 ms 119404 KB Output is correct
32 Correct 558 ms 260460 KB Output is correct
33 Correct 482 ms 260440 KB Output is correct
34 Correct 1069 ms 123544 KB Output is correct
35 Correct 1081 ms 123548 KB Output is correct
36 Correct 1072 ms 135916 KB Output is correct
37 Correct 1072 ms 135916 KB Output is correct
38 Correct 861 ms 133784 KB Output is correct
39 Correct 852 ms 133612 KB Output is correct
40 Correct 871 ms 133700 KB Output is correct