Submission #1056635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056635		mickey080929	Summer Driving (CCO24_day1problem3)	C++17	9 / 25	6062 ms	856704 KiB

Main

#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 (stderr)

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 / 1
• Subtask 2: 0 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 6
• Subtask 7: 0 / 2