oj.uz

Submission #1053598

# Submission time Handle Problem Language Result Execution time Memory
1053598 2024-08-11T14:10:30 Z Ejen Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 439 ms 83280 KB 
#include <bits/stdc++.h>

#define el '\n'
#define fu(i, a, b) for (long long i = a; i <= b; ++i)
#define fd(i, a, b) for (long long i = a; i >= b; --i)
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define sz(v)  (ll)v.size()
#define mask(i) (1LL << i)
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
typedef int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll Rand(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}

ll last(ll msk)    {return msk & (-msk);}
ll pop_cnt(ll msk) {return __builtin_popcountll(msk);}
ll ctz(ll msk)     {return __builtin_ctzll(msk);}
ll lg(ll msk)      {return 63 - __builtin_clzll(msk);}

template<class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if (a < b) {
            a = b;
            return true;
        }
        return false;
    }

template<class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if (a > b) {
            a = b;
            return true;
        }
        return false;
    }

template<class T>
    void print(T &a, string sep = " ", string stop = "\n") {
        for (auto x : a) cout << x << sep;
        cout << stop;
    }

template<class T>
    void compress(vector<T> &v) {
        sort(all(v));
        v.resize(unique(all(v)) - v.begin());
    }

const long long N = 1e6 + 27, base = 311, inf = 2e18, mod = 1e9 + 19972207;

ll n, t, m, timer, cur;
ll a[N], f[N], in[N], out[N], left[N];
vector<ll> adj[N];

void dfs(ll u, ll p) {
    in[u] = ++timer;
    vector<ll> tmp;
    for (ll v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        if (u == t) {
            if (in[v] <= in[m] && in[m] <= out[v]) {
                cout << f[v];
                exit(0);
            }
        }
        f[u] += f[v];
        if (in[v] > in[m] || in[m] > out[v]) {
            f[u]++;
            tmp.push_back(f[v]);
        }
    }
    out[u] = timer;
    if (in[u] <= in[m] && in[m] <= out[u] && tmp.empty()) cur++;
    sort(all(tmp));
    if (sz(tmp)) f[u] -= tmp.back();
    fd(i, sz(tmp) - 2, 0) {
        if (!cur) break;
        cur--;
        f[u] -= tmp[i];
    }
    
}

signed main() {
    // freopen("brentford40mu.inp", "r", stdin);
    // freopen("brentford40mu.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t >> m;
    if (t == m) return cout << 0, 0;
    fu(i, 2, n) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(t, 0);
    // fu(i, 1, n) cout << f[i] << ' ';
    // cout << f[t];
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB Output is correct
2 Correct 4 ms 29332 KB Output is correct
3 Correct 4 ms 29312 KB Output is correct
4 Correct 4 ms 29368 KB Output is correct
5 Correct 4 ms 29364 KB Output is correct
6 Correct 3 ms 29272 KB Output is correct
7 Correct 3 ms 29276 KB Output is correct
8 Correct 4 ms 29284 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 3 ms 29276 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 66644 KB Output is correct
2 Correct 143 ms 75140 KB Output is correct
3 Incorrect 439 ms 83280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB Output is correct
2 Correct 4 ms 29332 KB Output is correct
3 Correct 4 ms 29312 KB Output is correct
4 Correct 4 ms 29368 KB Output is correct
5 Correct 4 ms 29364 KB Output is correct
6 Correct 3 ms 29272 KB Output is correct
7 Correct 3 ms 29276 KB Output is correct
8 Correct 4 ms 29284 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 3 ms 29276 KB Output is correct
11 Incorrect 4 ms 29276 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB Output is correct
2 Correct 4 ms 29332 KB Output is correct
3 Correct 4 ms 29312 KB Output is correct
4 Correct 4 ms 29368 KB Output is correct
5 Correct 4 ms 29364 KB Output is correct
6 Correct 3 ms 29272 KB Output is correct
7 Correct 3 ms 29276 KB Output is correct
8 Correct 4 ms 29284 KB Output is correct
9 Correct 4 ms 29276 KB Output is correct
10 Correct 3 ms 29276 KB Output is correct
11 Correct 163 ms 66644 KB Output is correct
12 Correct 143 ms 75140 KB Output is correct
13 Incorrect 439 ms 83280 KB Output isn't correct
14 Halted 0 ms 0 KB -