oj.uz

답안 #563931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563931 2022-05-18T09:48:51 Z baokhue232005 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 468 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);
    }
    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;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 143064 KB Output is correct
2 Correct 65 ms 143192 KB Output is correct
3 Correct 70 ms 143176 KB Output is correct
4 Correct 68 ms 143204 KB Output is correct
5 Correct 67 ms 143136 KB Output is correct
6 Correct 66 ms 143112 KB Output is correct
7 Correct 65 ms 143136 KB Output is correct
8 Correct 68 ms 143176 KB Output is correct
9 Correct 68 ms 143144 KB Output is correct
10 Correct 66 ms 143128 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 468 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 143064 KB Output is correct
2 Correct 65 ms 143192 KB Output is correct
3 Correct 70 ms 143176 KB Output is correct
4 Correct 68 ms 143204 KB Output is correct
5 Correct 67 ms 143136 KB Output is correct
6 Correct 66 ms 143112 KB Output is correct
7 Correct 65 ms 143136 KB Output is correct
8 Correct 68 ms 143176 KB Output is correct
9 Correct 68 ms 143144 KB Output is correct
10 Correct 66 ms 143128 KB Output is correct
11 Correct 70 ms 143172 KB Output is correct
12 Incorrect 69 ms 143120 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 143064 KB Output is correct
2 Correct 65 ms 143192 KB Output is correct
3 Correct 70 ms 143176 KB Output is correct
4 Correct 68 ms 143204 KB Output is correct
5 Correct 67 ms 143136 KB Output is correct
6 Correct 66 ms 143112 KB Output is correct
7 Correct 65 ms 143136 KB Output is correct
8 Correct 68 ms 143176 KB Output is correct
9 Correct 68 ms 143144 KB Output is correct
10 Correct 66 ms 143128 KB Output is correct
11 Runtime error 468 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -