oj.uz

Submission #1056635

# Submission time Handle Problem Language Result Execution time Memory
1056635 2024-08-13T10:24:49 Z mickey080929 Summer Driving (CCO24_day1problem3) C++17
9 / 25
 6000 ms 856704 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 MN2{
    pair<int,int> val1, val2;
};

struct Node{
    int l, r;
    MN2 val;
};

MN2 Merge(MN2 u, MN2 v) {
    MN2 ret;
    if (u.val1 > v.val1) swap(u, v);
    ret.val1 = u.val1;
    ret.val2 = u.val2;
    if (v.val1.second != ret.val1.second && ret.val2 > v.val1)
        ret.val2 = v.val1;
    if (v.val2.second != ret.val1.second && ret.val2 > v.val2)
        ret.val2 = v.val2;
    return ret;
}

struct DynamicSegmentTree{
    vector<Node> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
    }
    void update(int node, int s, int e, int tar, pair<int,int> val) {
        tree[node].val = Merge(tree[node].val, {val, {inf,-1}});
        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, -1}, {inf,-1}}});
            }
            update(tree[node].l, s, mid, tar, val);
        }
        else {
            if (tree[node].r == -1) {
                tree[node].r = tree.size();
                tree.push_back({-1, -1, {{inf, -1}, {inf,-1}}});
            }
            update(tree[node].r, mid+1, e, tar, val);
        }
    }
    MN2 query(int node, int s, int e, int l, int r, bool f = false) {
        if (l > e || s > r || node == -1) return {{inf,-1}, {inf,-1}};
        if (l <= s && e <= r) return tree[node].val;
        int mid = s + e >> 1;
        return Merge(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, sub[x][lv]});
        }
        else {
            seg1[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
            seg2[c].update(0, 1, N, dist[x][lv], {val, sub[x][lv]});
        }
        
    }
}

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;
        MN2 t = seg2[c].query(0, 1, N, 1, d);
        //assert(t.val1.second != t.val2.second);
        if (t.val1.second == sub[x][lv]) ret = min(ret, t.val2.first);
        else ret = min(ret, t.val1.first);
    }
    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);
                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});
            }
            //cout << i << ' ' << dp[x] << ' ' << x << '\n';
        }
        
    }
    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, std::pair<int, int>)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In member function 'MN2 DynamicSegmentTree::query(int, int, int, int, int, bool)':
Main.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = s + e >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:345:21: warning: unused variable 'ret1' [-Wunused-variable]
  345 |                 int ret1 = Centquery(x);
      |                     ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67932 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 67932 KB Output is correct
5 Correct 9 ms 67832 KB Output is correct

Subtask #2
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3313 ms 851988 KB Output is correct
2 Correct 3329 ms 856704 KB Output is correct
3 Correct 4571 ms 853040 KB Output is correct
4 Execution timed out 6052 ms 421272 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 80476 KB Output is correct
2 Correct 11 ms 80604 KB Output is correct
3 Correct 11 ms 80424 KB Output is correct
4 Correct 11 ms 80476 KB Output is correct
5 Correct 10 ms 80476 KB Output is correct
6 Correct 10 ms 80476 KB Output is correct
7 Correct 11 ms 80412 KB Output is correct
8 Correct 10 ms 80412 KB Output is correct
9 Correct 9 ms 67932 KB Output is correct
10 Correct 11 ms 80612 KB Output is correct
11 Correct 11 ms 80732 KB Output is correct
12 Correct 10 ms 80404 KB Output is correct
13 Correct 12 ms 80220 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 80476 KB Output is correct
2 Correct 11 ms 80604 KB Output is correct
3 Correct 11 ms 80424 KB Output is correct
4 Correct 11 ms 80476 KB Output is correct
5 Correct 10 ms 80476 KB Output is correct
6 Correct 10 ms 80476 KB Output is correct
7 Correct 11 ms 80412 KB Output is correct
8 Correct 10 ms 80412 KB Output is correct
9 Correct 9 ms 67932 KB Output is correct
10 Correct 11 ms 80612 KB Output is correct
11 Correct 11 ms 80732 KB Output is correct
12 Correct 10 ms 80404 KB Output is correct
13 Correct 12 ms 80220 KB Output is correct
14 Correct 18 ms 81956 KB Output is correct
15 Correct 18 ms 82268 KB Output is correct
16 Correct 17 ms 82024 KB Output is correct
17 Correct 18 ms 82264 KB Output is correct
18 Correct 22 ms 82012 KB Output is correct
19 Correct 17 ms 82216 KB Output is correct
20 Correct 19 ms 82268 KB Output is correct
21 Correct 14 ms 81664 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 28 ms 82012 KB Output is correct
24 Correct 19 ms 82508 KB Output is correct
25 Correct 45 ms 82588 KB Output is correct
26 Correct 17 ms 82520 KB Output is correct
27 Correct 13 ms 80988 KB Output is correct
28 Correct 19 ms 81176 KB Output is correct
29 Correct 19 ms 80984 KB Output is correct
30 Correct 38 ms 81244 KB Output is correct
31 Correct 68 ms 81244 KB Output is correct
32 Correct 35 ms 81244 KB Output is correct
33 Correct 33 ms 84828 KB Output is correct

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 189520 KB Output is correct
2 Correct 1078 ms 198616 KB Output is correct
3 Correct 911 ms 192084 KB Output is correct
4 Correct 870 ms 199688 KB Output is correct
5 Correct 1161 ms 192256 KB Output is correct
6 Correct 1078 ms 199596 KB Output is correct
7 Correct 692 ms 199248 KB Output is correct
8 Correct 305 ms 175700 KB Output is correct
9 Correct 873 ms 200624 KB Output is correct
10 Correct 639 ms 202324 KB Output is correct
11 Correct 441 ms 202312 KB Output is correct
12 Correct 252 ms 160724 KB Output is correct
13 Correct 9 ms 67932 KB Output is correct
14 Correct 9 ms 67932 KB Output is correct
15 Correct 646 ms 190968 KB Output is correct
16 Execution timed out 6062 ms 149196 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 80476 KB Output is correct
2 Correct 11 ms 80604 KB Output is correct
3 Correct 11 ms 80424 KB Output is correct
4 Correct 11 ms 80476 KB Output is correct
5 Correct 10 ms 80476 KB Output is correct
6 Correct 10 ms 80476 KB Output is correct
7 Correct 11 ms 80412 KB Output is correct
8 Correct 10 ms 80412 KB Output is correct
9 Correct 9 ms 67932 KB Output is correct
10 Correct 11 ms 80612 KB Output is correct
11 Correct 11 ms 80732 KB Output is correct
12 Correct 10 ms 80404 KB Output is correct
13 Correct 12 ms 80220 KB Output is correct
14 Correct 18 ms 81956 KB Output is correct
15 Correct 18 ms 82268 KB Output is correct
16 Correct 17 ms 82024 KB Output is correct
17 Correct 18 ms 82264 KB Output is correct
18 Correct 22 ms 82012 KB Output is correct
19 Correct 17 ms 82216 KB Output is correct
20 Correct 19 ms 82268 KB Output is correct
21 Correct 14 ms 81664 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 28 ms 82012 KB Output is correct
24 Correct 19 ms 82508 KB Output is correct
25 Correct 45 ms 82588 KB Output is correct
26 Correct 17 ms 82520 KB Output is correct
27 Correct 13 ms 80988 KB Output is correct
28 Correct 19 ms 81176 KB Output is correct
29 Correct 19 ms 80984 KB Output is correct
30 Correct 38 ms 81244 KB Output is correct
31 Correct 68 ms 81244 KB Output is correct
32 Correct 35 ms 81244 KB Output is correct
33 Correct 33 ms 84828 KB Output is correct
34 Correct 1217 ms 190292 KB Output is correct
35 Correct 1075 ms 199532 KB Output is correct
36 Correct 833 ms 190720 KB Output is correct
37 Correct 891 ms 199724 KB Output is correct
38 Correct 1137 ms 192280 KB Output is correct
39 Correct 985 ms 199848 KB Output is correct
40 Correct 757 ms 200840 KB Output is correct
41 Correct 343 ms 175448 KB Output is correct
42 Correct 9 ms 67928 KB Output is correct
43 Correct 4175 ms 189372 KB Output is correct
44 Execution timed out 6044 ms 150600 KB Time limit exceeded
45 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67932 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 67932 KB Output is correct
5 Correct 9 ms 67832 KB Output is correct
6 Correct 3313 ms 851988 KB Output is correct
7 Correct 3329 ms 856704 KB Output is correct
8 Correct 4571 ms 853040 KB Output is correct
9 Execution timed out 6052 ms 421272 KB Time limit exceeded
10 Halted 0 ms 0 KB -