oj.uz

Submission #563954

# Submission time Handle Problem Language Result Execution time Memory
563954 2022-05-18T10:00:28 Z baokhue232005 Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 764 ms 241332 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const int mod = 998244353;
const int maxN = 2000005;
int n, a[maxN];
int x, y, z, k;
int s, t;

bool sacred[maxN];
int godlist[maxN];
int cn = 0;
vector<int> road[maxN];
int szi[maxN];
vector<int> burden[maxN];
vector<int> vc[maxN];

bool dfs_sacred(int node, int par){
    if(node == t){
        sacred[node] = 1; return 1;
    }
    for(int cc : vc[node]){
        if(dfs_sacred(cc, node)){
            sacred[node] = 1;
            godlist[++cn] = node; return 1;
        }
    }
    return 0;
}

int dfs_calc(int node, int par){
    for(int i = 0; i < (int)vc[node].size(); ++i){
        if(vc[node][i] == par){
            vc[node].erase(vc[node].begin() + i); break;
        }
    }
    for(int &cc : vc[node]) cc = dfs_calc(cc, node);
    sort(all(vc[node]), greater<int>());
    int res = 0;
    if(vc[node].size() >= 2) res = vc[node][1];
    return res + vc[node].size();
}

bool solve(int node, int lim, int turn){
    ++turn;
    if(node > n) return (lim >= 0);
    int fail = 0;
    for(int cc : road[node]) if(cc + szi[node] > lim) ++fail;
    if(turn < fail) return 0;
    turn -= fail; lim -= fail;
    return solve(node + 1, lim, turn);
}

signed main(){
    // freopen("mousetrap.inp", "r", stdin);
    // freopen("mousetrap.out", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> t >> s;
    if(s == t){
        cout << 0 << endl; exit(0);
    }
    memset(sacred, 0, sizeof(sacred));
    for1(i, 2, n){
        cin >> x >> y;
        vc[x].pb(y);
        vc[y].pb(x);
    }
    // if(n > 10) exit(0);
    dfs_sacred(s, s);
    reverse(godlist + 1, godlist + cn + 1);
    z = 0;
    vector<ii> dawut;
    for1(i, 1, n) if(!sacred[i]){
        int saved = 0;
        for(int cc : vc[i]) if(sacred[cc] && cc != t)
            dawut.pb({i, cc});
    }
    for(ii pr : dawut){
        burden[pr.se].pb(dfs_calc(pr.fi, pr.se));
    }
    // if(n > 10) exit(0);
    n = cn;
    for1(i, 1, n){
        swap(road[i], burden[godlist[i]]);
        szi[i] = road[i].size();
        // cout << szi[i] << endl;
        // for(int cc : road[i]) cout << cc << " ";
        // cout << endl;
    }
    z = 0;
    for2(i, n, 1){
        z += szi[i]; szi[i] = z;
    }
    int le = 0, ri = 1e7;
    while(le != ri){
        int mid = (le + ri) / 2;
        if(solve(1, mid, 0)) ri = mid;
        else le = mid + 1;
    }
    cout << le << endl;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:95:13: warning: unused variable 'saved' [-Wunused-variable]
   95 |         int saved = 0;
      |             ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 143124 KB Output is correct
2 Correct 67 ms 143128 KB Output is correct
3 Correct 66 ms 143172 KB Output is correct
4 Correct 67 ms 143180 KB Output is correct
5 Correct 69 ms 143076 KB Output is correct
6 Correct 65 ms 143152 KB Output is correct
7 Correct 65 ms 143056 KB Output is correct
8 Correct 66 ms 143160 KB Output is correct
9 Correct 70 ms 143176 KB Output is correct
10 Correct 68 ms 143156 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 175948 KB Output is correct
2 Correct 369 ms 175652 KB Output is correct
3 Correct 713 ms 179960 KB Output is correct
4 Correct 404 ms 163940 KB Output is correct
5 Correct 764 ms 180104 KB Output is correct
6 Correct 707 ms 179908 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 143124 KB Output is correct
2 Correct 67 ms 143128 KB Output is correct
3 Correct 66 ms 143172 KB Output is correct
4 Correct 67 ms 143180 KB Output is correct
5 Correct 69 ms 143076 KB Output is correct
6 Correct 65 ms 143152 KB Output is correct
7 Correct 65 ms 143056 KB Output is correct
8 Correct 66 ms 143160 KB Output is correct
9 Correct 70 ms 143176 KB Output is correct
10 Correct 68 ms 143156 KB Output is correct
11 Correct 68 ms 143132 KB Output is correct
12 Correct 71 ms 143112 KB Output is correct
13 Correct 66 ms 143192 KB Output is correct
14 Correct 67 ms 143180 KB Output is correct
15 Correct 68 ms 143340 KB Output is correct
16 Correct 66 ms 143116 KB Output is correct
17 Correct 69 ms 143148 KB Output is correct
18 Correct 75 ms 143112 KB Output is correct
19 Correct 76 ms 143120 KB Output is correct
20 Correct 68 ms 143168 KB Output is correct
21 Correct 71 ms 143180 KB Output is correct
22 Correct 68 ms 143136 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 143124 KB Output is correct
2 Correct 67 ms 143128 KB Output is correct
3 Correct 66 ms 143172 KB Output is correct
4 Correct 67 ms 143180 KB Output is correct
5 Correct 69 ms 143076 KB Output is correct
6 Correct 65 ms 143152 KB Output is correct
7 Correct 65 ms 143056 KB Output is correct
8 Correct 66 ms 143160 KB Output is correct
9 Correct 70 ms 143176 KB Output is correct
10 Correct 68 ms 143156 KB Output is correct
11 Correct 340 ms 175948 KB Output is correct
12 Correct 369 ms 175652 KB Output is correct
13 Correct 713 ms 179960 KB Output is correct
14 Correct 404 ms 163940 KB Output is correct
15 Correct 764 ms 180104 KB Output is correct
16 Correct 707 ms 179908 KB Output is correct
17 Correct 68 ms 143132 KB Output is correct
18 Correct 71 ms 143112 KB Output is correct
19 Correct 66 ms 143192 KB Output is correct
20 Correct 67 ms 143180 KB Output is correct
21 Correct 68 ms 143340 KB Output is correct
22 Correct 66 ms 143116 KB Output is correct
23 Correct 69 ms 143148 KB Output is correct
24 Correct 75 ms 143112 KB Output is correct
25 Correct 76 ms 143120 KB Output is correct
26 Correct 68 ms 143168 KB Output is correct
27 Correct 71 ms 143180 KB Output is correct
28 Correct 68 ms 143136 KB Output is correct
29 Correct 75 ms 143112 KB Output is correct
30 Correct 337 ms 178676 KB Output is correct
31 Correct 358 ms 178892 KB Output is correct
32 Correct 393 ms 233672 KB Output is correct
33 Correct 357 ms 241332 KB Output is correct
34 Correct 719 ms 179916 KB Output is correct
35 Correct 716 ms 180000 KB Output is correct
36 Correct 756 ms 190004 KB Output is correct
37 Correct 734 ms 190180 KB Output is correct
38 Correct 532 ms 190692 KB Output is correct
39 Correct 535 ms 190648 KB Output is correct
40 Correct 553 ms 191196 KB Output is correct