oj.uz

Submission #563938

# Submission time Handle Problem Language Result Execution time Memory
563938 2022-05-18T09:50:47 Z baokhue232005 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 541 ms 524288 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 < 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;
    for1(i, 1, n) if(!sacred[i]){
        int saved = 0;
        for(int cc : vc[i]) if(sacred[cc]) saved = cc;
        if(saved){
            burden[saved].pb(dfs_calc(i, saved));
        }
    }
    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;
    }
    if(n > 10) exit(0);
    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 dfs_calc(int, int)':
mousetrap.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < vc[node].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 143176 KB Output is correct
2 Correct 67 ms 143180 KB Output is correct
3 Correct 68 ms 143124 KB Output is correct
4 Correct 65 ms 143116 KB Output is correct
5 Correct 68 ms 143180 KB Output is correct
6 Correct 65 ms 143172 KB Output is correct
7 Correct 64 ms 143080 KB Output is correct
8 Correct 66 ms 143152 KB Output is correct
9 Correct 67 ms 143180 KB Output is correct
10 Correct 70 ms 143176 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 541 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 143176 KB Output is correct
2 Correct 67 ms 143180 KB Output is correct
3 Correct 68 ms 143124 KB Output is correct
4 Correct 65 ms 143116 KB Output is correct
5 Correct 68 ms 143180 KB Output is correct
6 Correct 65 ms 143172 KB Output is correct
7 Correct 64 ms 143080 KB Output is correct
8 Correct 66 ms 143152 KB Output is correct
9 Correct 67 ms 143180 KB Output is correct
10 Correct 70 ms 143176 KB Output is correct
11 Correct 66 ms 143064 KB Output is correct
12 Incorrect 69 ms 143212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 143176 KB Output is correct
2 Correct 67 ms 143180 KB Output is correct
3 Correct 68 ms 143124 KB Output is correct
4 Correct 65 ms 143116 KB Output is correct
5 Correct 68 ms 143180 KB Output is correct
6 Correct 65 ms 143172 KB Output is correct
7 Correct 64 ms 143080 KB Output is correct
8 Correct 66 ms 143152 KB Output is correct
9 Correct 67 ms 143180 KB Output is correct
10 Correct 70 ms 143176 KB Output is correct
11 Runtime error 541 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -