oj.uz

Submission #1056047

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

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

const int inf = 1e9;

struct SegmentTree{
    vector<int> tree;
    void init(int n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, inf);
    }
    void update(int node, int s, int e, int l, int r, int val) {
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            tree[node] = min(tree[node], val);
            return;
        }
        int mid = s + e >> 1;
        update(node*2, s, mid, l, r, val);
        update(node*2+1, mid+1, e, l, r, val);
    }
    int query(int node, int s, int e, int tar) {
        if (s == e) return tree[node];
        int mid = s + e >> 1;
        if (tar <= mid) return min(tree[node], query(node*2, s, mid, tar));
        return min(tree[node], query(node*2+1, mid+1, e, tar));
    }
};

/*struct Node{
    int l, r, val;
};

struct DynamicSegmentTree{
    vector<Node> tree;

};*/

SegmentTree seg;

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

void dfs(int x, int p) {
    sz[x] = 1;
    down[x] = 0;
    for (auto &y : adj[x]) {
        if (y == p) continue;
        par[y] = x;
        dep[y] = dep[x] + 1;
        g[x].push_back(y);
        dfs(y, x);
        down[x] = max(down[x], down[y] + 1);
        //if (sz[g[x][0]] < sz[y]) swap(g[x][0], g[x].back());
        sz[x] += sz[y];
    }
}

void dfs2(int x) {
    in[x] = ++ pv;
    for (auto &y : g[x]) {
        top[y] = y;
        dfs2(y);
    }
    out[x] = pv;
}

void HLDupdate(int x) {
    int cnt = B;
    while (x) {
        int tp = top[x];
        assert(tp == x);
        if (dep[x] - dep[tp] + 1 < cnt) {
            seg.update(1, 1, N, in[tp], in[x], x);
            cnt -= dep[x] - dep[tp] + 1;
        }
        else {
            seg.update(1, 1, N, in[x]-cnt+1, in[x], x);
            break;
        }
        x = par[tp];
    }
}

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);
    top[R] = R;
    dfs2(R);
    seg.init(N);
    int mxdep = 0;
    for (int i=1; i<=N; i++) {
        mxdep = max(mxdep, dep[i]);
        vtx[dep[i]].push_back(i);
        HLDupdate(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], seg.query(1, 1, N, in[x]));
            }
            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 = R;
        for (auto &x : vtx[1]) {
            ans = min(ans, dp[x]);
        }
        cout << ans;
    }
    else {
        int ans = 0;
        for (auto &x : vtx[1]) {
            if (down[x] >= A-1)
                ans = max(ans, dp[x]);
        }
        cout << ans;
    }
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(int)':
Main.cpp:12:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
Main.cpp:21:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
Main.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23896 KB Output is correct
2 Correct 3 ms 23732 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 8 ms 21596 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 87892 KB Output is correct
2 Correct 732 ms 87892 KB Output is correct
3 Execution timed out 6039 ms 87636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 8 ms 21592 KB Output is correct
3 Correct 7 ms 21672 KB Output is correct
4 Incorrect 4 ms 25948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 8 ms 21592 KB Output is correct
3 Correct 7 ms 21672 KB Output is correct
4 Incorrect 4 ms 25948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 35936 KB Output is correct
2 Correct 602 ms 31708 KB Output is correct
3 Correct 496 ms 31604 KB Output is correct
4 Correct 407 ms 31892 KB Output is correct
5 Correct 715 ms 31648 KB Output is correct
6 Correct 597 ms 31816 KB Output is correct
7 Incorrect 238 ms 31832 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 8 ms 21592 KB Output is correct
3 Correct 7 ms 21672 KB Output is correct
4 Incorrect 4 ms 25948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23896 KB Output is correct
2 Correct 3 ms 23732 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 8 ms 21596 KB Output is correct
6 Correct 639 ms 87892 KB Output is correct
7 Correct 732 ms 87892 KB Output is correct
8 Execution timed out 6039 ms 87636 KB Time limit exceeded
9 Halted 0 ms 0 KB -