Submission #699117

#	Time	Username	Problem	Language	Result	Execution time	Memory
699117		qwerasdfzxcl	Road Closures (APIO21_roads)	C++17	12 / 100	210 ms	83012 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
struct Edge{
    int v, w, i;
    Edge(){}
    Edge(int _v, int _w, int _i): v(_v), w(_w), i(_i) {}
};

int n;
vector<pair<int, int>> adj[100100];
list<Edge> G[100100];
pair<int, int> dep[100100];
int dcnt, in[100100], out[100100], pW[100100], deg[100100];
ll dp[100100][2];

int pt, k;
vector<int> V, on;

struct Node1{
    ll sum, c, mn;
    Node1(){}
    Node1(ll x): sum(x), c(1), mn(x) {}
    Node1(ll _s, ll _c, ll _mn): sum(_s), c(_c), mn(_mn) {}

    Node1 operator + (const Node1 &N) const{
        return Node1(sum + N.sum, c + N.c, min(mn, N.mn));
    }
};
struct Seg1{
    vector<Node1> tree;
    int sz;

    void update(int i, int l, int r, int p, ll x){
        if (p<l || r<p) return;
        if (l==r){
            tree[i] = Node1(x);
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, p, x); update(i<<1|1, m+1, r, p, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }

    int _search_below(int i, int l, int r, ll x){
        if (tree[i].mn > x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int ret = _search_below(i<<1|1, m+1, r, x);
        if (ret==-1) return _search_below(i<<1, l, m, x);
        return ret;
    }

    int _search_cnt(int i, int l, int r, int c){
        if (l==r) return l;

        int m = (l+r)>>1;
        if (tree[i<<1].c < c) return _search_cnt(i<<1|1, m+1, r, c - tree[i<<1].c);
        return _search_cnt(i<<1, l, m, c);
    }

    Node1 query(int i, int l, int r, int s, int e){
        if (r<s || e<l) return Node1(0, 0, 0);
        if (s<=l && r<=e) return tree[i];

        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }

    void init(int _sz){sz = _sz; tree.clear(); tree.resize(sz*4 + 2, Node1(0, 0, 0));}
    void update(int p, ll x){
        //printf(" update %d %lld\n", p, x);
        update(1, 1, sz, p, x);
    }
    int count(ll x){
        int idx = _search_below(1, 1, sz, x);
        return query(1, 1, sz, 1, idx).c;
    }
    ll query(int c){
        int idx = _search_cnt(1, 1, sz, c);
        //printf("  query %d -> %d\n", c, idx);
        return query(1, 1, sz, 1, idx).sum;
    }
}tree[100100];

struct Seg2{
    pair<int, int> tree[200200];
    int sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = dep[i-sz];
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }

    pair<int, int> query(int l, int r){
        ++r;
        pair<int, int> ret = {INF1, 0};
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}rmq;

void dfs0(int s, int pa = 0, int paw = 0){
    on.push_back(s);

    pW[s] = paw;
    in[s] = ++dcnt;
    deg[s] = adj[s].size();
    dep[in[s]] = {dep[pa].first + 1, s};

    sort(adj[s].begin(), adj[s].end());
    for (auto &[w, v]:adj[s]) if (v!=pa){
        G[s].emplace_back(v, w, G[s].size() + 1);
        dfs0(v, s, w);
    }

    tree[s].init(G[s].size());
    out[s] = dcnt;
}

ll calc(int s, const vector<pair<ll, ll>> &C, int t){
    int cnt = 0;
    ll ret = 0;
    for (int i=0;i<(int)C.size();i++){
        auto [x, y] = C[i];
        if (x > y || tree[s].count(y-x) + i + 1 <= t){
            cnt++;
            ret += y-x;
        }
        else break;
    }

    ret += tree[s].query(t-cnt);

    //printf(" calc %d %d -> %d %lld\n", s, t, cnt, ret);

    return ret;
}

bool cmp(const pair<ll, ll> &x, const pair<ll, ll> &y) {return x.second-x.first < y.second-y.first;}

void dfs(int s){
    //printf("in %d\n", s);
    auto iter = G[s].begin();
    vector<pair<ll, ll>> C;

    while(pt < (int)V.size() && in[V[pt]] <= out[s]){
        while (in[V[pt]] > out[iter->v]){
            tree[s].update(iter->i, iter->w);
            iter = G[s].erase(iter);
        }
        //printf(" s = %d pointing %d\n", s, iter->v);

        int v = V[pt];
        pt++;
        dfs(v);

        if (iter->v == v){
            C.emplace_back(dp[v][0], dp[v][1]);
        }
        else{
            ll val = min(dp[v][0], dp[v][1]);
            C.emplace_back(val, val + iter->w);
        }

        iter++;
    }

    while (iter!=G[s].end()){
        tree[s].update(iter->i, iter->w);
        iter = G[s].erase(iter);
    }

    dp[s][0] = 0, dp[s][1] = pW[s];

    if (deg[s] <= k){
        for (auto &[x, y]:C){
            dp[s][0] += min(x, y);
            dp[s][1] += min(x, y);
        }
        //printf("k = %d, s = %d -> %lld %lld\n", k, s, dp[s][0], dp[s][1]);
        return;
    }

    for (auto &[x, y]:C){
        dp[s][0] += x;
        dp[s][1] += x;
    }

    sort(C.begin(), C.end(), cmp);

    dp[s][0] += calc(s, C, deg[s]-k);
    dp[s][1] += calc(s, C, deg[s]-k-1);

    //printf("k = %d, s = %d -> %lld %lld\n", k, s, dp[s][0], dp[s][1]);
}

int lca(int x, int y){
    assert(in[x] < in[y]);
    auto [d, s] = rmq.query(in[x], in[y]);
    return s;
}

bool cmp2(int x, int y){return in[x] < in[y];}

void getV(const vector<int> &on){
    pt = 1;
    V.clear();
    V.push_back(1);
    for (int i=0;i<(int)on.size();i++){
        V.push_back(on[i]);
        if (i) V.push_back(lca(on[i-1], on[i]));
    }

    sort(V.begin(), V.end(), cmp2);
    V.erase(unique(V.begin(), V.end()), V.end());
}

void getnxt(vector<int> &on, int k){
    vector<int> nxt;
    for (auto &x:on) if (deg[x] >= k) nxt.push_back(x);
    swap(on, nxt);
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    vector<ll> ans(1);
    for (int i=0;i<n-1;i++){
        adj[U[i]+1].emplace_back(W[i], V[i]+1);
        adj[V[i]+1].emplace_back(W[i], U[i]+1);
        ans[0] += W[i];
    }

    dfs0(1);
    rmq.init(n+1);

    for (k=1;k<=n-1;k++){
        getV(on);

        dfs(1);
        ans.push_back(dp[1][0]);

        getnxt(on, k+1);
    }

    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22