oj.uz

Submission #1056067

# Submission time Handle Problem Language Result Execution time Memory
1056067 2024-08-13T07:34:38 Z 정민찬(#11068) Summer Driving (CCO24_day1problem3) C++17
9 / 25
 6000 ms 87888 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 == g[x][0] ? top[x] : y;
        dfs2(y);
    }
    out[x] = pv;
}

void HLDupdate(int x) {
    int ori = x;
    int cnt = B;
    while (x) {
        int tp = top[x];
        if (dep[x] - dep[tp] + 1 < cnt) {
            seg.update(1, 1, N, in[tp], in[x], ori);
            cnt -= dep[x] - dep[tp] + 1;
        }
        else {
            seg.update(1, 1, N, in[x]-cnt+1, in[x], ori);
            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 8 ms 21596 KB Output is correct
2 Correct 7 ms 21604 KB Output is correct
3 Correct 7 ms 21428 KB Output is correct
4 Correct 7 ms 21596 KB Output is correct
5 Correct 7 ms 21596 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 87888 KB Output is correct
2 Correct 515 ms 87888 KB Output is correct
3 Correct 2355 ms 87640 KB Output is correct
4 Execution timed out 6094 ms 85532 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21592 KB Output is correct
2 Correct 7 ms 21596 KB Output is correct
3 Correct 7 ms 21460 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 7 ms 21596 KB Output is correct
6 Correct 11 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21572 KB Output is correct
9 Correct 8 ms 21592 KB Output is correct
10 Correct 7 ms 21592 KB Output is correct
11 Correct 7 ms 21608 KB Output is correct
12 Correct 7 ms 21596 KB Output is correct
13 Correct 10 ms 21636 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21592 KB Output is correct
2 Correct 7 ms 21596 KB Output is correct
3 Correct 7 ms 21460 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 7 ms 21596 KB Output is correct
6 Correct 11 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21572 KB Output is correct
9 Correct 8 ms 21592 KB Output is correct
10 Correct 7 ms 21592 KB Output is correct
11 Correct 7 ms 21608 KB Output is correct
12 Correct 7 ms 21596 KB Output is correct
13 Correct 10 ms 21636 KB Output is correct
14 Correct 10 ms 21852 KB Output is correct
15 Correct 9 ms 21852 KB Output is correct
16 Correct 9 ms 21848 KB Output is correct
17 Correct 9 ms 21852 KB Output is correct
18 Correct 13 ms 21724 KB Output is correct
19 Correct 9 ms 21852 KB Output is correct
20 Correct 9 ms 21852 KB Output is correct
21 Correct 8 ms 21900 KB Output is correct
22 Correct 7 ms 21596 KB Output is correct
23 Correct 19 ms 21928 KB Output is correct
24 Correct 10 ms 21852 KB Output is correct
25 Correct 33 ms 21860 KB Output is correct
26 Correct 8 ms 21848 KB Output is correct
27 Correct 8 ms 21852 KB Output is correct
28 Correct 11 ms 21852 KB Output is correct
29 Correct 8 ms 21852 KB Output is correct
30 Correct 51 ms 21852 KB Output is correct
31 Correct 31 ms 21848 KB Output is correct
32 Correct 58 ms 21848 KB Output is correct
33 Correct 17 ms 22108 KB Output is correct

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 31588 KB Output is correct
2 Correct 612 ms 31820 KB Output is correct
3 Correct 515 ms 31532 KB Output is correct
4 Correct 387 ms 34760 KB Output is correct
5 Correct 807 ms 31648 KB Output is correct
6 Correct 623 ms 31572 KB Output is correct
7 Correct 283 ms 34684 KB Output is correct
8 Correct 125 ms 30800 KB Output is correct
9 Correct 598 ms 31572 KB Output is correct
10 Correct 403 ms 31724 KB Output is correct
11 Correct 103 ms 31384 KB Output is correct
12 Correct 74 ms 31564 KB Output is correct
13 Correct 7 ms 21516 KB Output is correct
14 Correct 10 ms 21848 KB Output is correct
15 Correct 279 ms 30764 KB Output is correct
16 Execution timed out 6049 ms 31836 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 21592 KB Output is correct
2 Correct 7 ms 21596 KB Output is correct
3 Correct 7 ms 21460 KB Output is correct
4 Correct 8 ms 21596 KB Output is correct
5 Correct 7 ms 21596 KB Output is correct
6 Correct 11 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21572 KB Output is correct
9 Correct 8 ms 21592 KB Output is correct
10 Correct 7 ms 21592 KB Output is correct
11 Correct 7 ms 21608 KB Output is correct
12 Correct 7 ms 21596 KB Output is correct
13 Correct 10 ms 21636 KB Output is correct
14 Correct 10 ms 21852 KB Output is correct
15 Correct 9 ms 21852 KB Output is correct
16 Correct 9 ms 21848 KB Output is correct
17 Correct 9 ms 21852 KB Output is correct
18 Correct 13 ms 21724 KB Output is correct
19 Correct 9 ms 21852 KB Output is correct
20 Correct 9 ms 21852 KB Output is correct
21 Correct 8 ms 21900 KB Output is correct
22 Correct 7 ms 21596 KB Output is correct
23 Correct 19 ms 21928 KB Output is correct
24 Correct 10 ms 21852 KB Output is correct
25 Correct 33 ms 21860 KB Output is correct
26 Correct 8 ms 21848 KB Output is correct
27 Correct 8 ms 21852 KB Output is correct
28 Correct 11 ms 21852 KB Output is correct
29 Correct 8 ms 21852 KB Output is correct
30 Correct 51 ms 21852 KB Output is correct
31 Correct 31 ms 21848 KB Output is correct
32 Correct 58 ms 21848 KB Output is correct
33 Correct 17 ms 22108 KB Output is correct
34 Correct 895 ms 31612 KB Output is correct
35 Correct 691 ms 32576 KB Output is correct
36 Correct 471 ms 34460 KB Output is correct
37 Correct 450 ms 34648 KB Output is correct
38 Correct 785 ms 34456 KB Output is correct
39 Correct 629 ms 32372 KB Output is correct
40 Correct 223 ms 32492 KB Output is correct
41 Correct 70 ms 32876 KB Output is correct
42 Correct 4 ms 22616 KB Output is correct
43 Correct 3433 ms 31688 KB Output is correct
44 Execution timed out 6084 ms 35544 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21596 KB Output is correct
2 Correct 7 ms 21604 KB Output is correct
3 Correct 7 ms 21428 KB Output is correct
4 Correct 7 ms 21596 KB Output is correct
5 Correct 7 ms 21596 KB Output is correct
6 Correct 558 ms 87888 KB Output is correct
7 Correct 515 ms 87888 KB Output is correct
8 Correct 2355 ms 87640 KB Output is correct
9 Execution timed out 6094 ms 85532 KB Time limit exceeded
10 Halted 0 ms 0 KB -