oj.uz

Submission #157205

# Submission time Handle Problem Language Result Execution time Memory
157205 2019-10-10T05:19:00 Z lyc Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 465 ms 90456 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 1e6+5;

int N, T, M, A, B;
vector<int> al[MX_N];
int w[MX_N], d[MX_N], pa[MX_N];
vector<ii> sub[MX_N];

void dfs(int u, int p) {
    for (auto v : al[u]) if (v != p) {
        pa[v] = u;
        d[v] = d[u] + 1;
        w[v] = w[u] + SZ(al[u])-1-(p!=0);
        dfs(v,u);
    }
    if (SZ(al[u]) != 1) {
        int a = 0, b = 0;
        for (auto v : al[u]) if (v != p) {
            if (w[v] > a) a = w[v];
            else if (w[v] > b) b = w[v];
        }
        if (b) w[u] = b;
        else ++w[u];
    }
    //cout << u << " (" << w[u] << ")\n";
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> T >> M;
    FOR(i,1,N-1){
        cin >> A >> B;
        al[A].push_back(B);
        al[B].push_back(A);
    }

    dfs(T,0);
    int lo = -1, hi = 2*N;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;

        int p, u, i, b, bad = 0;
        for (p = -1, u = M, i = 0, b = 0; pa[u] != 0; p = u, u = pa[u], ++i) {
            //cout << "\tTRAVERSE " << u << endl;
            int x = 0;
            for (int v : al[u]) if (v != pa[u] && v != p) {
                //cout << "\t\tNEI " << v << " :: " << w[v] << endl;
                if (w[v]+(d[v]-d[u])+b > mid) ++x;
            }
            b += x;
            if (b > i+1) bad = 1;
        }
        if (b > mid) bad = 1;

        //cout << mid << " :: " << bad << endl;
        (bad ? lo : hi) = mid;
    }

    cout << hi << '\n';
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 46 ms 47272 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Incorrect 46 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 90456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 46 ms 47272 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Incorrect 46 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 46 ms 47272 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Incorrect 46 ms 47352 KB Output isn't correct
8 Halted 0 ms 0 KB -