oj.uz

Submission #1055878

# Submission time Handle Problem Language Result Execution time Memory
1055878 2024-08-13T06:15:08 Z 정민찬(#11068) Summer Driving (CCO24_day1problem3) C++17
1 / 25
 6000 ms 64852 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

int N, R, A, B;
vector<int> adj[300010];
int down[300010], par[300010];
int dep[300010];
int in[300010], out[300010];
int pv;

void dfs(int x, int p) {
    down[x] = 0;
    in[x] = ++ pv;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        par[y] = x;
        dep[y] = dep[x] + 1;
        dfs(y, x);
        down[x] = max(down[x], down[y] + 1);
    }
    out[x] = pv;
}

int findmin(int x, int p, int dist) {
    if (dist > B-1) return N + 1;
    int ret = x;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        ret = min(ret, findmin(y, x, dist+1));
    }
    return ret;
}

int dp[300010];
int dp2[300010];

int simulate(int x, int p, int dist) {
    if (dist > B) return N + 1;
    int ret;
    int d = 0;
    for (auto &y : adj[x]) {
        if (y == p || y == par[x]) continue;
        d = max(d, down[y] + 1);
    }
    if (d < A) {
        ret = x;
        for (auto &y : adj[x]) {
            if (y == p || y == par[x]) continue;
            ret = min(ret, dp[y]);
        }
    }
    else {
        ret = 0;
        for (auto &y : adj[x]) {
            if (y == p || y == par[x]) continue;
            if (down[y] >= A-1)
                ret = max(ret, dp[y]);
        }
    }
    for (auto &y : adj[x]) {
        if (y == p) continue;
        ret = min(ret, simulate(y, x, dist + 1));
    }
    return ret;
}
vector<int> vtx[300010];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> R >> A >> B;
    if (A <= B) {
        cout << "1\n";
        return 0;
    }
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(R, 0);
    int mxdep = 0;
    for (int i=1; i<=N; i++) {
        mxdep = max(mxdep, dep[i]);
        vtx[dep[i]].push_back(i);
    }
    for (int i=mxdep; i>=1; i--) {
        if (i+A-1 <= mxdep) {
            for (auto &x : vtx[i+A-1]) {
                dp2[x] = simulate(x, -1, 0);
            }
        }
        for (auto &x : vtx[i]) {
            if (down[x] < A-1) {
                dp[x] = min(par[x], findmin(x, par[x], 0));
            }
            else {
                for (auto &y : vtx[i+A-1]) {
                    if (in[x] <= in[y] && in[y] <= out[x])
                        dp[x] = max(dp[x], dp2[y]);
                }
            }
        }
    }
    if (down[R] < A) {
        int ans = 0;
        for (auto &x : vtx[1]) {
            ans = max(ans, dp[x]);
        }
        cout << ans << '\n';
    }
    else {
        int ans = 0;
        for (auto &x : vtx[1]) {
            if (down[x] >= A-1)
                ans = max(ans, dp[x]);
        }
        cout << ans << '\n';
    }
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14464 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 64848 KB Output is correct
2 Correct 306 ms 64852 KB Output is correct
3 Correct 2299 ms 64648 KB Output is correct
4 Execution timed out 6061 ms 62576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 5 ms 14556 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 6 ms 14608 KB Output is correct
7 Correct 5 ms 14556 KB Output is correct
8 Incorrect 5 ms 14428 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 5 ms 14556 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 6 ms 14608 KB Output is correct
7 Correct 5 ms 14556 KB Output is correct
8 Incorrect 5 ms 14428 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 21076 KB Output is correct
2 Correct 516 ms 22224 KB Output is correct
3 Correct 403 ms 22252 KB Output is correct
4 Correct 316 ms 22104 KB Output is correct
5 Correct 658 ms 22292 KB Output is correct
6 Correct 544 ms 22164 KB Output is correct
7 Correct 195 ms 22096 KB Output is correct
8 Incorrect 37 ms 21904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 5 ms 14556 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 6 ms 14608 KB Output is correct
7 Correct 5 ms 14556 KB Output is correct
8 Incorrect 5 ms 14428 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 5 ms 14428 KB Output is correct
3 Correct 5 ms 14464 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 294 ms 64848 KB Output is correct
7 Correct 306 ms 64852 KB Output is correct
8 Correct 2299 ms 64648 KB Output is correct
9 Execution timed out 6061 ms 62576 KB Time limit exceeded
10 Halted 0 ms 0 KB -