oj.uz

Submission #705598

# Submission time Handle Problem Language Result Execution time Memory
705598 2023-03-04T18:25:51 Z Kahou Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1748 ms 161896 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6 + 50;
ll n, t, m, val[N], dp[N], ps[N], k; 
bool mark[N];
vector<int> adj[N];
vector<int> vp;
vector<pii> vc;

void dfs(int u, int p=0) {
        if (u == t) return;
        int mx1 = 0, mx2 = 0;
        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
                if (mark[v]) {
                        mark[u] = 1;
                        val[u] = val[v] + (int)adj[u].size()-1-(p>0);
                }
                else {
                        if (dp[v] > mx1) {
                                mx2 = mx1;
                                mx1 = dp[v];
                        }
                        else if (dp[v] > mx2) {
                                mx2 = dp[v];
                        }
                }
        }
        if (!mark[u]) {
                dp[u] = (int)adj[u].size()-(p>0) + mx2;
        }
        else {
                vp.push_back(u);
                for (int v:adj[u]) {
                        if (v == p) continue;
                        if (mark[v]) continue;
                        vc.push_back({u, dp[v] + val[u]});
                }
        }
}

bool isval(ll x) {
        int id = 0;
        int tmp = 0;
        for (pii p:vc) {
                while (id < p.F) {
                        ps[id+1] = ps[id];
                        tmp = ps[id];
                        id++;
                }
                if (tmp+p.S > x) {
                        ps[id]++;
                }
        }
        for (int i = 1; i <= k; i++) {
                if (ps[i] > i || ps[i] > x) return 0;
        }
        return 1;
}
void solve() {
        cin >> n >> t >> m;
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        mark[t] = 1;
        dfs(m);
        reverse(vp.begin(), vp.end());
        reverse(vc.begin(), vc.end());
        for (pii &x : vc) {
                while (x.F != vp[k]) k++;
                x.F = k+1;
                cerr << x.F << ' ' << x.S << endl;
        }
        k = vp.size();
        ll dw = -1, up = 1e9;
        while (up-dw > 1) {
                ll md = (up+dw)>>1;
                if (isval(md)) up = md;
                else dw = md;
        }
        cout << up << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        solve();
        return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23736 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 11 ms 23824 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 11 ms 23704 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 62896 KB Output is correct
2 Correct 246 ms 59000 KB Output is correct
3 Correct 651 ms 64076 KB Output is correct
4 Correct 284 ms 43888 KB Output is correct
5 Correct 631 ms 64056 KB Output is correct
6 Correct 620 ms 64168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23736 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 11 ms 23824 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 11 ms 23704 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23892 KB Output is correct
13 Correct 12 ms 23884 KB Output is correct
14 Correct 13 ms 23924 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23880 KB Output is correct
18 Correct 13 ms 23892 KB Output is correct
19 Correct 13 ms 23836 KB Output is correct
20 Correct 13 ms 23892 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 12 ms 23764 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23736 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 11 ms 23824 KB Output is correct
5 Correct 11 ms 23736 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 13 ms 23764 KB Output is correct
10 Correct 11 ms 23704 KB Output is correct
11 Correct 265 ms 62896 KB Output is correct
12 Correct 246 ms 59000 KB Output is correct
13 Correct 651 ms 64076 KB Output is correct
14 Correct 284 ms 43888 KB Output is correct
15 Correct 631 ms 64056 KB Output is correct
16 Correct 620 ms 64168 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 12 ms 23892 KB Output is correct
19 Correct 12 ms 23884 KB Output is correct
20 Correct 13 ms 23924 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 12 ms 23764 KB Output is correct
23 Correct 12 ms 23880 KB Output is correct
24 Correct 13 ms 23892 KB Output is correct
25 Correct 13 ms 23836 KB Output is correct
26 Correct 13 ms 23892 KB Output is correct
27 Correct 13 ms 23892 KB Output is correct
28 Correct 12 ms 23764 KB Output is correct
29 Correct 12 ms 23712 KB Output is correct
30 Correct 302 ms 62956 KB Output is correct
31 Correct 264 ms 63048 KB Output is correct
32 Correct 337 ms 161896 KB Output is correct
33 Correct 293 ms 156764 KB Output is correct
34 Correct 768 ms 64052 KB Output is correct
35 Correct 662 ms 64232 KB Output is correct
36 Correct 1737 ms 79872 KB Output is correct
37 Correct 1748 ms 79796 KB Output is correct
38 Correct 935 ms 79684 KB Output is correct
39 Correct 939 ms 79444 KB Output is correct
40 Correct 974 ms 93164 KB Output is correct