oj.uz

Submission #1053454

# Submission time Handle Problem Language Result Execution time Memory
1053454 2024-08-11T12:04:25 Z ilovveyyou Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 458 ms 81492 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))
#define max_rng *max_element
#define min_rng *min_element

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a)); a.resize(unique(all(a)) - a.begin());
    }

const ll oo = (ll) 1e18, inf = (ll) 1e9, mod = (ll) 1e9 + 7;
const int mxn = (int) 1e6 + 5, S = (int) 450, S2 = (int) 450, lg = (int) 18;

void add(ll &x, ll y) {
    x += y;
    if (x >= mod) x -= mod;
}
void sub(ll &x, ll y) {
    x -= y;
    if (x < 0) x += mod;
}
int n, t, m;
vector<int> g[mxn];

int timer = 0;
int in[mxn], out[mxn];

int par[mxn], dist[mxn], h[mxn];

void dfs(int u, int p) {
    in[u] = ++timer;
    if (u != t) {
        for (int v : g[u]) if (v != p)
            dist[u]++;
    }
    for (int v : g[u]) if (v != p) {
        dist[v] += dist[u];
        h[v] = h[u] + 1;
        dfs(v, u);
        par[v] = u;
    }
    out[u] = timer;
}
bool inRoot(int r, int u) {
    return in[r] <= in[u] && in[u] <= out[r];
}

int f[mxn], ban[mxn];
int dp(int u, int p, int blocked) {

    if (f[u] != -1) return f[u];

    int adj = 0;
    for (int v : g[u]) if (v != p && !ban[v]) 
        adj++;

    if (adj <= blocked + 1) {
        // cout << "HA " << u << ' ' << adj << "\n\n";
        return f[u] = adj;
    }

    f[u] = inf;
    int sz = g[u].size();
    vector<int> k(sz, -inf), h(sz, -inf);

    for (int i = 0; i < sz; ++i) {
        int v = g[u][i];
        if (v != p && !ban[v])
            k[i] = h[i] = dp(v, u, blocked) + adj;
    }
    for (int i = 1; i < sz; ++i) {
        // int v = g[u][i];
        // if (v != p && !ban[v])
        maximize(k[i], k[i-1]);
    }
    for (int i = sz-2; i >= 0; --i) {
        // int v = g[u][i];
        maximize(h[i], h[i+1]);
    }

    // cout << "PHASE BEGIN u = " << u << ' ' << p << '\n';
    // for (int i = 0; i < sz; ++i) {
    //     int v = g[u][i];
    //     if (v != p && !ban[v]) {
    //         cout << i << ' ' << v << ' ' << k[i] << ' ' << h[i] << '\n';
    //     }
    // }

    for (int i = 0; i < sz; ++i) {
        int v = g[u][i];
        if (v == p || ban[v]) continue;
        int cur = -inf;
        if (i > 0) maximize(cur, k[i-1]);
        if (i+1 < sz) maximize(cur, h[i+1]);
        if (cur != -inf) minimize(f[u], cur);
    }
    // cout << "Phase ended with F[u] = " << f[u] << "\n\n";
    return f[u];
}

int backtrack(int cur, int blocked = 0) {
    if (cur == t) return -inf;
    int res = dp(cur, par[cur], blocked);
    res += dist[par[cur]] - h[par[cur]];
    ban[cur] = true; f[cur] = 0;
    // cout << cur << ' ' << par[cur] << ' ' << blocked << ' ' << res << ' ' << dist[par[cur]] - h[par[cur]] << "\n\n\n";
    return max(res, backtrack(par[cur], blocked+1));
}

void solve() {
    cin >> n >> t >> m;
    for (int i = 2; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (t == m) {
        cout << 0 << '\n';
        return;
    }

    memset(f, -1, sizeof f);

    dfs(t, 0);

    cout << backtrack(m);

    return;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define TASK "task"
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.";

    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36700 KB Output is correct
2 Correct 6 ms 36700 KB Output is correct
3 Correct 4 ms 36700 KB Output is correct
4 Correct 4 ms 36700 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 4 ms 36700 KB Output is correct
8 Correct 4 ms 36776 KB Output is correct
9 Correct 4 ms 36700 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 80212 KB Output is correct
2 Correct 171 ms 76920 KB Output is correct
3 Correct 444 ms 81320 KB Output is correct
4 Correct 167 ms 63952 KB Output is correct
5 Correct 440 ms 81492 KB Output is correct
6 Correct 458 ms 81484 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36700 KB Output is correct
2 Correct 6 ms 36700 KB Output is correct
3 Correct 4 ms 36700 KB Output is correct
4 Correct 4 ms 36700 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 4 ms 36700 KB Output is correct
8 Correct 4 ms 36776 KB Output is correct
9 Correct 4 ms 36700 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Incorrect 5 ms 36776 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36700 KB Output is correct
2 Correct 6 ms 36700 KB Output is correct
3 Correct 4 ms 36700 KB Output is correct
4 Correct 4 ms 36700 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 4 ms 36700 KB Output is correct
8 Correct 4 ms 36776 KB Output is correct
9 Correct 4 ms 36700 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 175 ms 80212 KB Output is correct
12 Correct 171 ms 76920 KB Output is correct
13 Correct 444 ms 81320 KB Output is correct
14 Correct 167 ms 63952 KB Output is correct
15 Correct 440 ms 81492 KB Output is correct
16 Correct 458 ms 81484 KB Output is correct
17 Incorrect 5 ms 36776 KB Output isn't correct
18 Halted 0 ms 0 KB -