oj.uz

Submission #1053456

# Submission time Handle Problem Language Result Execution time Memory
1053456 2024-08-11T12:06:08 Z ilovveyyou Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 486 ms 81496 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) {
        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) {
        maximize(k[i], k[i-1]);
    }
    for (int i = sz-2; i >= 0; --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);
    }
    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]];
    // cout << cur << ' ' << par[cur] << ' ' << blocked << ' ' << f[cur] << ' ' << dist[par[cur]] - h[par[cur]] << "\n\n\n";
    ban[cur] = true; f[cur] = 0;
    
    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);

    ll ans = backtrack(m);
    assert(ans < inf);

    cout << ans;

    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:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".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 5 ms 36788 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 5 ms 36696 KB Output is correct
5 Correct 5 ms 36776 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36700 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 4 ms 36568 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 167 ms 80204 KB Output is correct
2 Correct 153 ms 76696 KB Output is correct
3 Correct 476 ms 81468 KB Output is correct
4 Correct 202 ms 63828 KB Output is correct
5 Correct 484 ms 81480 KB Output is correct
6 Correct 486 ms 81496 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 5 ms 36788 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 5 ms 36696 KB Output is correct
5 Correct 5 ms 36776 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36700 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 4 ms 36568 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Incorrect 5 ms 36700 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 5 ms 36788 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 5 ms 36696 KB Output is correct
5 Correct 5 ms 36776 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36700 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 4 ms 36568 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 167 ms 80204 KB Output is correct
12 Correct 153 ms 76696 KB Output is correct
13 Correct 476 ms 81468 KB Output is correct
14 Correct 202 ms 63828 KB Output is correct
15 Correct 484 ms 81480 KB Output is correct
16 Correct 486 ms 81496 KB Output is correct
17 Incorrect 5 ms 36700 KB Output isn't correct
18 Halted 0 ms 0 KB -