oj.uz

Submission #705580

# Submission time Handle Problem Language Result Execution time Memory
705580 2023-03-04T17:09:25 Z Kahou Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 684 ms 67252 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;
int n, t, m, val[N], dp[N], ps[N], k; 
bool mark[N];
vector<int> adj[N];
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] + 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] = adj[u].size()-(p>0) + mx2;
        }
        else {
                for (int v:adj[u]) {
                        if (v == p) continue;
                        if (mark[v]) continue;
                        vc.push_back({u, dp[v] + val[u]});
                }
        }
}

bool isval(int x) {
        int prv = 0;
        int tmp = 0;
        for (pii p:vc) {
                if (p.F != prv) {
                        ps[p.F] = ps[prv];
                        tmp = ps[prv];
                        prv = p.F;
                }
                if (tmp+p.S > x) {
                        ps[p.F]++;
                }
                if (ps[p.F] > min(p.F, 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(vc.begin(), vc.end());
        int prv= 0;
        for (pii &x : vc) {
                if (x.F != prv) {
                        prv = x.F;
                        k++;
                }
                x.F = k;
        }
        int dw = -1, up = 1e9;
        while (up-dw > 1) {
                int 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Correct 14 ms 23836 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 65920 KB Output is correct
2 Correct 247 ms 62432 KB Output is correct
3 Correct 664 ms 67076 KB Output is correct
4 Correct 301 ms 46460 KB Output is correct
5 Correct 655 ms 67252 KB Output is correct
6 Correct 684 ms 67212 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Correct 14 ms 23836 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Correct 14 ms 23836 KB Output is correct
5 Incorrect 12 ms 23812 KB Output isn't correct
6 Halted 0 ms 0 KB -