oj.uz

Submission #973316

# Submission time Handle Problem Language Result Execution time Memory
973316 2024-05-01T18:23:28 Z efedmrlr Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 667 ms 178808 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 1e6 + 5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,t,m;

vector<int> dp(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<vector<int> > vs(N, vector<int>());
vector<int > suf;
int mxd = 0;
void dfs(int node, int par) {
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs(c, node);
    }
    array<int, 2> mx = {0, 0};
    for(auto c : adj[node]) {
        if(c == par) continue;
        if(dp[c] > mx[0]) {
            swap(mx[0], mx[1]);
            mx[0] = dp[c];
        }
        else if(dp[c] > mx[1]) {
            mx[1] = dp[c];
        }
    }
    dp[node] = mx[1] + (int)adj[node].size() - 1; 

}

int dfs2(int node, int par, int dist = 0) {
    if(node == t) {
        mxd = dist;
        return node;
    }
    int ret = 0;
    for(auto c : adj[node]) {
        if(c == par) continue;
        ret = dfs2(c, node, dist + 1);
        if(ret) {
            break;
        }
    }
    if(!ret) return 0;
    for(auto c : adj[node]) {
        if(c == par || c == ret) continue;
        dfs(c, node);
        vs[dist].pb(dp[c]);
        // cout << "c:" << c << " dp:" << dp[c] << " dist:" << dist << "\n";
    }
    return node;
}

bool check(int tar) {
    int stam = 1;
    for(int i = 0; i < mxd; i++) {
        int used = 0;
        for(auto c : vs[i]) {
            if(c + suf[i] > tar) {
                if(!stam) return 0;
                stam--;
                used++;
            }
        }
        tar -= used;
        if(tar < 0) return 0;
        stam++;
    }
    return 1;
}

inline void solve() {
    cin>>n>>t>>m;
    REP(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs2(m, 0);
    for(int i = 0; i < mxd; i++) {
        sort(rall(vs[i]));
    }
    suf.assign(mxd + 3, 0);
    for(int i = mxd - 1; i>=0; i--) {
        suf[i] = suf[i + 1] + (int)vs[i].size();
    }
    int tl = 0, tr = n;
    while(tl < tr) {
        int tm = (tl + tr) >> 1;
        if(check(tm)) {
            tr = tm;
        }
        else {
            tl = tm + 1;
        }
    } 
    if(!check(tl)) tl++;
    cout << tl << "\n"; 
    
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51152 KB Output is correct
2 Correct 16 ms 51288 KB Output is correct
3 Correct 16 ms 51292 KB Output is correct
4 Correct 16 ms 51292 KB Output is correct
5 Correct 16 ms 51292 KB Output is correct
6 Correct 16 ms 51292 KB Output is correct
7 Correct 15 ms 51292 KB Output is correct
8 Correct 16 ms 51292 KB Output is correct
9 Correct 16 ms 51292 KB Output is correct
10 Correct 15 ms 51188 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 82568 KB Output is correct
2 Correct 205 ms 79696 KB Output is correct
3 Correct 591 ms 83524 KB Output is correct
4 Correct 249 ms 67464 KB Output is correct
5 Correct 554 ms 83744 KB Output is correct
6 Correct 583 ms 83744 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51152 KB Output is correct
2 Correct 16 ms 51288 KB Output is correct
3 Correct 16 ms 51292 KB Output is correct
4 Correct 16 ms 51292 KB Output is correct
5 Correct 16 ms 51292 KB Output is correct
6 Correct 16 ms 51292 KB Output is correct
7 Correct 15 ms 51292 KB Output is correct
8 Correct 16 ms 51292 KB Output is correct
9 Correct 16 ms 51292 KB Output is correct
10 Correct 15 ms 51188 KB Output is correct
11 Correct 16 ms 51288 KB Output is correct
12 Correct 17 ms 51544 KB Output is correct
13 Correct 17 ms 51292 KB Output is correct
14 Correct 16 ms 51288 KB Output is correct
15 Correct 17 ms 51356 KB Output is correct
16 Correct 16 ms 51360 KB Output is correct
17 Correct 16 ms 51292 KB Output is correct
18 Correct 16 ms 51292 KB Output is correct
19 Correct 16 ms 51364 KB Output is correct
20 Correct 17 ms 51288 KB Output is correct
21 Correct 17 ms 51292 KB Output is correct
22 Correct 16 ms 51288 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51152 KB Output is correct
2 Correct 16 ms 51288 KB Output is correct
3 Correct 16 ms 51292 KB Output is correct
4 Correct 16 ms 51292 KB Output is correct
5 Correct 16 ms 51292 KB Output is correct
6 Correct 16 ms 51292 KB Output is correct
7 Correct 15 ms 51292 KB Output is correct
8 Correct 16 ms 51292 KB Output is correct
9 Correct 16 ms 51292 KB Output is correct
10 Correct 15 ms 51188 KB Output is correct
11 Correct 218 ms 82568 KB Output is correct
12 Correct 205 ms 79696 KB Output is correct
13 Correct 591 ms 83524 KB Output is correct
14 Correct 249 ms 67464 KB Output is correct
15 Correct 554 ms 83744 KB Output is correct
16 Correct 583 ms 83744 KB Output is correct
17 Correct 16 ms 51288 KB Output is correct
18 Correct 17 ms 51544 KB Output is correct
19 Correct 17 ms 51292 KB Output is correct
20 Correct 16 ms 51288 KB Output is correct
21 Correct 17 ms 51356 KB Output is correct
22 Correct 16 ms 51360 KB Output is correct
23 Correct 16 ms 51292 KB Output is correct
24 Correct 16 ms 51292 KB Output is correct
25 Correct 16 ms 51364 KB Output is correct
26 Correct 17 ms 51288 KB Output is correct
27 Correct 17 ms 51292 KB Output is correct
28 Correct 16 ms 51288 KB Output is correct
29 Correct 17 ms 51108 KB Output is correct
30 Correct 227 ms 95824 KB Output is correct
31 Correct 228 ms 95828 KB Output is correct
32 Correct 332 ms 178808 KB Output is correct
33 Correct 275 ms 158740 KB Output is correct
34 Correct 583 ms 97152 KB Output is correct
35 Correct 584 ms 96976 KB Output is correct
36 Correct 667 ms 107856 KB Output is correct
37 Correct 667 ms 107932 KB Output is correct
38 Correct 507 ms 109960 KB Output is correct
39 Correct 482 ms 109716 KB Output is correct
40 Correct 445 ms 109908 KB Output is correct