oj.uz

Submission #563927

# Submission time Handle Problem Language Result Execution time Memory
563927 2022-05-18T09:45:16 Z baokhue232005 Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 571 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];
vector<int> godlist;
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.pb(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);
    }
    dfs_sacred(s, s);
    godlist.pb(0);
    reverse(all(godlist));
    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 = godlist.size() - 1;
    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 dfs_calc(int, int)':
mousetrap.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i < vc[node].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 143056 KB Output is correct
2 Correct 69 ms 143088 KB Output is correct
3 Correct 77 ms 143120 KB Output is correct
4 Correct 69 ms 143168 KB Output is correct
5 Correct 78 ms 143116 KB Output is correct
6 Correct 70 ms 143128 KB Output is correct
7 Correct 70 ms 143052 KB Output is correct
8 Correct 80 ms 143136 KB Output is correct
9 Correct 69 ms 143168 KB Output is correct
10 Correct 72 ms 143180 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 571 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 67 ms 143056 KB Output is correct
2 Correct 69 ms 143088 KB Output is correct
3 Correct 77 ms 143120 KB Output is correct
4 Correct 69 ms 143168 KB Output is correct
5 Correct 78 ms 143116 KB Output is correct
6 Correct 70 ms 143128 KB Output is correct
7 Correct 70 ms 143052 KB Output is correct
8 Correct 80 ms 143136 KB Output is correct
9 Correct 69 ms 143168 KB Output is correct
10 Correct 72 ms 143180 KB Output is correct
11 Correct 76 ms 143152 KB Output is correct
12 Incorrect 76 ms 143264 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 143056 KB Output is correct
2 Correct 69 ms 143088 KB Output is correct
3 Correct 77 ms 143120 KB Output is correct
4 Correct 69 ms 143168 KB Output is correct
5 Correct 78 ms 143116 KB Output is correct
6 Correct 70 ms 143128 KB Output is correct
7 Correct 70 ms 143052 KB Output is correct
8 Correct 80 ms 143136 KB Output is correct
9 Correct 69 ms 143168 KB Output is correct
10 Correct 72 ms 143180 KB Output is correct
11 Runtime error 571 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -