oj.uz

Submission #1056434

# Submission time Handle Problem Language Result Execution time Memory
1056434 2024-08-13T09:25:35 Z mickey080929 Summer Driving (CCO24_day1problem3) C++17
9 / 25
 6000 ms 612636 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;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, inf});
    }
    void update(int node, int s, int e, int tar, int val, bool f = false) {
        tree[node].val = min(tree[node].val, val);
        if (s == e) {    
            return;
        }
        int mid = s + e >> 1;
        if (tar <= mid) {
            if (tree[node].l == -1) {
                tree[node].l = tree.size();
                tree.push_back({-1, -1, inf});
            }
            update(tree[node].l, s, mid, tar, val, f);
        }
        else {
            if (tree[node].r == -1) {
                tree[node].r = tree.size();
                tree.push_back({-1, -1, inf});
            }
            update(tree[node].r, mid+1, e, tar, val, f);
        }
    }
    int query(int node, int s, int e, int l, int r, bool f = false) {
        if (l > e || s > r || node == -1) return inf;
        if (l <= s && e <= r) return tree[node].val;
        int mid = s + e >> 1;
        return min(query(tree[node].l, s, mid, l, r, f), query(tree[node].r, mid+1, e, l, r, f));
    }
};

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];

int chk[300010];

int getSize(int x, int p) {
    sz[x] = 1;
    for (auto &y : adj[x]) {
        if (chk[y] || y == p) continue;
        sz[x] += getSize(y, x);
    }
    return sz[x];
}

int getCent(int x, int p, int cap) {
    for (auto &y : adj[x]) {
        if (chk[y] || y == p) continue;
        if (sz[y] * 2 > cap)
            return getCent(y, x, cap);
    }
    return x;
}

set<int> ps[300010];
int cent[300010][20], dist[300010][20];
int sub[300010][20];

void dfs3(int x, int p, int lv, int S) {
    sub[x][lv] = S;
    for (auto &y : adj[x]) {
        if (y == p || chk[y]) continue;
        cent[y][lv] = cent[x][lv];
        dist[y][lv] = dist[x][lv] + 1;
        dfs3(y, x, lv, S);
    }
}

void dnc(int x, int lv) {
    x = getCent(x, -1, getSize(x, -1));
    int t = x;
    while (t && !chk[t]) {
        ps[x].insert(t);
        t = par[t];
    }
    sub[x][lv] = x;
    cent[x][lv] = x;
    dist[x][lv] = 0;
    for (auto &y : adj[x]) {
        if (chk[y]) continue;
        cent[y][lv] = x;
        dist[y][lv] = 1;
        dfs3(y, x, lv, y);
    }
    chk[x] = 1;
    for (auto &y : adj[x]) {
        if (chk[y]) continue;
        dnc(y, lv+1);
    }
}

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 dp[300010];
int dp2[300010];

vector<int> vtx[300010];
vector<pair<int,int>> poss[300010], imp[300010];
DynamicSegmentTree seg1[300010], seg2[300010];

void CentUpdate(int x) {
    for (int lv=19; lv>=0; lv--) {
        if (!cent[x][lv]) continue;
        if (cent[x][lv] == x) continue;
        int c = cent[x][lv];
        int val;
        if (poss[x].empty()) val = imp[x][0].first;
        else val = poss[x][0].first;
        if (sub[x][lv] == par[c]) {
            if (ps[c].find(x) != ps[c].end()) {
                if (poss[x].empty()) {
                    if (ps[c].find(imp[x][0].second) != ps[c].end())
                        val = imp[x][1].first;
                }
                else if (poss[x].size() == 1) {
                    if (ps[c].find(poss[x][0].second) != ps[c].end())
                        val = imp[x][0].first;
                }
                else {
                    if (ps[c].find(poss[x][0].second) != ps[c].end())
                        val = poss[x][1].first;
                }
            }
            seg1[c].update(0, 1, N, dist[x][lv], val);
        }
        else {
            seg1[c].update(0, 1, N, dist[x][lv], val);
            seg2[c].update(0, 1, N, dist[x][lv], val);
        }
    }
}

int Centquery(int x) {
    int ret = N + 1;
    for (int lv=19; lv>=0; lv--) {
        if (!cent[x][lv]) continue;
        int d = B - dist[x][lv];
        if (d < 0) continue;
        int c = cent[x][lv];
        int val;
        if (poss[c].empty()) val = imp[c][0].first;
        else val = poss[c][0].first;
        if (x == c) {
            ret = min(ret, val);
        }
        else {
            if (poss[c].empty()) {
                if (sub[x][lv] == imp[c][0].second)
                    val = imp[c][1].first;
            }
            else if (poss[c].size() == 1) {
                if (sub[x][lv] == poss[c][0].second)
                    val = imp[c][0].first;
            }
            else {
                if (sub[x][lv] == poss[c][0].second)
                    val = poss[c][1].first;
            }
            ret = min(ret, val);
        }
        if (d == 0) continue;
        if (sub[x][lv] == par[c]) {
            ret = min(ret, seg2[c].query(0, 1, N, 1, d));
        }
        else {
            ret = min(ret, seg1[c].query(0, 1, N, 1, d));
        }
    }
    assert(ret != N+1);
    return ret;
}

//DynamicSegmentTree final[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;
}

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);
        imp[i].push_back({i, -1});
        seg1[i].init();
        seg2[i].init();
    }
    dnc(1, 0);
    for (int i=mxdep; i>=1; i--) {
        for (auto &x : vtx[i]) {
            sort(imp[x].begin(), imp[x].end());
            sort(poss[x].begin(), poss[x].end());
            reverse(poss[x].begin(), poss[x].end());
            CentUpdate(x);
        }
        if (i+A-1 <= mxdep) {
            for (auto &x : vtx[i+A-1]) {
                int ret1 = Centquery(x);
                int ret2 = simulate(x, -1, 0);
                assert(ret1 <= ret2);
                dp2[x] = ret2;
            }
        }
        for (auto &x : vtx[i]) {
            if (down[x] < A-1) {
                dp[x] = min(par[x], seg.query(1, 1, N, in[x]));
                imp[par[x]].push_back({dp[x], 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]);
                }
                poss[par[x]].push_back({dp[x], x});
            }
        }
        
    }
    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;
      |                   ~~^~~
Main.cpp: In member function 'void DynamicSegmentTree::update(int, int, int, int, int, bool)':
Main.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int DynamicSegmentTree::query(int, int, int, int, int, bool)':
Main.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = s + e >> 1;
      |                   ~~^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 67860 KB Output is correct
2 Correct 9 ms 67932 KB Output is correct
3 Correct 9 ms 67932 KB Output is correct
4 Correct 9 ms 68048 KB Output is correct
5 Correct 9 ms 68084 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3244 ms 612636 KB Output is correct
2 Correct 3193 ms 611968 KB Output is correct
3 Correct 4299 ms 610312 KB Output is correct
4 Execution timed out 6049 ms 392800 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 80396 KB Output is correct
2 Correct 10 ms 80368 KB Output is correct
3 Correct 14 ms 80536 KB Output is correct
4 Correct 11 ms 80524 KB Output is correct
5 Correct 11 ms 80472 KB Output is correct
6 Correct 11 ms 80548 KB Output is correct
7 Correct 11 ms 80548 KB Output is correct
8 Correct 11 ms 80476 KB Output is correct
9 Correct 9 ms 67928 KB Output is correct
10 Correct 11 ms 80476 KB Output is correct
11 Correct 11 ms 80632 KB Output is correct
12 Correct 12 ms 80216 KB Output is correct
13 Correct 11 ms 80368 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 80396 KB Output is correct
2 Correct 10 ms 80368 KB Output is correct
3 Correct 14 ms 80536 KB Output is correct
4 Correct 11 ms 80524 KB Output is correct
5 Correct 11 ms 80472 KB Output is correct
6 Correct 11 ms 80548 KB Output is correct
7 Correct 11 ms 80548 KB Output is correct
8 Correct 11 ms 80476 KB Output is correct
9 Correct 9 ms 67928 KB Output is correct
10 Correct 11 ms 80476 KB Output is correct
11 Correct 11 ms 80632 KB Output is correct
12 Correct 12 ms 80216 KB Output is correct
13 Correct 11 ms 80368 KB Output is correct
14 Correct 16 ms 81524 KB Output is correct
15 Correct 17 ms 81756 KB Output is correct
16 Correct 16 ms 81500 KB Output is correct
17 Correct 19 ms 81760 KB Output is correct
18 Correct 16 ms 81624 KB Output is correct
19 Correct 19 ms 81752 KB Output is correct
20 Correct 19 ms 81788 KB Output is correct
21 Correct 14 ms 81372 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 27 ms 81572 KB Output is correct
24 Correct 19 ms 81756 KB Output is correct
25 Correct 47 ms 81880 KB Output is correct
26 Correct 17 ms 81756 KB Output is correct
27 Correct 13 ms 81104 KB Output is correct
28 Correct 13 ms 81016 KB Output is correct
29 Correct 13 ms 80984 KB Output is correct
30 Correct 40 ms 81244 KB Output is correct
31 Correct 42 ms 81260 KB Output is correct
32 Correct 37 ms 81240 KB Output is correct
33 Correct 30 ms 83560 KB Output is correct

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 158372 KB Output is correct
2 Correct 964 ms 164268 KB Output is correct
3 Correct 813 ms 159760 KB Output is correct
4 Correct 732 ms 164200 KB Output is correct
5 Correct 1016 ms 159880 KB Output is correct
6 Correct 938 ms 164176 KB Output is correct
7 Correct 701 ms 163564 KB Output is correct
8 Correct 310 ms 150972 KB Output is correct
9 Correct 913 ms 164308 KB Output is correct
10 Correct 700 ms 165728 KB Output is correct
11 Correct 432 ms 165708 KB Output is correct
12 Correct 264 ms 142832 KB Output is correct
13 Correct 13 ms 67928 KB Output is correct
14 Correct 10 ms 67932 KB Output is correct
15 Correct 591 ms 157768 KB Output is correct
16 Execution timed out 6026 ms 136672 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 80396 KB Output is correct
2 Correct 10 ms 80368 KB Output is correct
3 Correct 14 ms 80536 KB Output is correct
4 Correct 11 ms 80524 KB Output is correct
5 Correct 11 ms 80472 KB Output is correct
6 Correct 11 ms 80548 KB Output is correct
7 Correct 11 ms 80548 KB Output is correct
8 Correct 11 ms 80476 KB Output is correct
9 Correct 9 ms 67928 KB Output is correct
10 Correct 11 ms 80476 KB Output is correct
11 Correct 11 ms 80632 KB Output is correct
12 Correct 12 ms 80216 KB Output is correct
13 Correct 11 ms 80368 KB Output is correct
14 Correct 16 ms 81524 KB Output is correct
15 Correct 17 ms 81756 KB Output is correct
16 Correct 16 ms 81500 KB Output is correct
17 Correct 19 ms 81760 KB Output is correct
18 Correct 16 ms 81624 KB Output is correct
19 Correct 19 ms 81752 KB Output is correct
20 Correct 19 ms 81788 KB Output is correct
21 Correct 14 ms 81372 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 27 ms 81572 KB Output is correct
24 Correct 19 ms 81756 KB Output is correct
25 Correct 47 ms 81880 KB Output is correct
26 Correct 17 ms 81756 KB Output is correct
27 Correct 13 ms 81104 KB Output is correct
28 Correct 13 ms 81016 KB Output is correct
29 Correct 13 ms 80984 KB Output is correct
30 Correct 40 ms 81244 KB Output is correct
31 Correct 42 ms 81260 KB Output is correct
32 Correct 37 ms 81240 KB Output is correct
33 Correct 30 ms 83560 KB Output is correct
34 Correct 1114 ms 158036 KB Output is correct
35 Correct 974 ms 164104 KB Output is correct
36 Correct 688 ms 158292 KB Output is correct
37 Correct 796 ms 164332 KB Output is correct
38 Correct 1020 ms 159656 KB Output is correct
39 Correct 918 ms 164436 KB Output is correct
40 Correct 682 ms 164948 KB Output is correct
41 Correct 289 ms 150468 KB Output is correct
42 Correct 10 ms 68100 KB Output is correct
43 Correct 4198 ms 156360 KB Output is correct
44 Execution timed out 6053 ms 138060 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 67860 KB Output is correct
2 Correct 9 ms 67932 KB Output is correct
3 Correct 9 ms 67932 KB Output is correct
4 Correct 9 ms 68048 KB Output is correct
5 Correct 9 ms 68084 KB Output is correct
6 Correct 3244 ms 612636 KB Output is correct
7 Correct 3193 ms 611968 KB Output is correct
8 Correct 4299 ms 610312 KB Output is correct
9 Execution timed out 6049 ms 392800 KB Time limit exceeded
10 Halted 0 ms 0 KB -