Submission #1095543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095543		vladilius	Designated Cities (JOI19_designated_cities)	C++17	39 / 100	2089 ms	62016 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const ll inf = numeric_limits<ll> :: max();
 
struct ST{
    vector<pair<ll, int>> t;
    vector<ll> a, p;
    int n;
    ST(int ns){
        n = ns;
        a.resize(n + 1);
        t.resize(4 * n);
        p.resize(4 * n);
    }
    void upd(int p, ll x){
        a[p] = x;
    }
    void build(int v, int tl, int tr){
        if (tl == tr){
            t[v] = {a[tl], tl};
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        build(vv, tl, tm);
        build(vv + 1, tm + 1, tr);
        t[v] = max(t[vv], t[vv + 1]);
    }
    void build(){
        fill(p.begin(), p.end(), 0);
        build(1, 1, n);
    }
    pair<ll, int> get(){
        return t[1];
    }
    void push(int& v){
        if (!p[v]) return;
        int vv = 2 * v;
        t[vv].ff += p[v]; p[vv] += p[v];
        t[vv + 1].ff += p[v]; p[vv + 1] += p[v];
        p[v] = 0;
    }
    void add(int v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v].ff += x;
            p[v] += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
        t[v] = max(t[vv], t[vv + 1]);
    }
    void add(int l, int r, int x){
        if (l > r) return;
        add(1, 1, n, l, r, x);
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<arr3> g[n + 1];
    ll tot = 0;
    for (int i = 1; i < n; i++){
        int a, b, c, d; cin>>a>>b>>c>>d;
        tot += c; tot += d;
        g[a].pb({b, c, d});
        g[b].pb({a, d, c});
    }
    
    int q; cin>>q;
    vector<int> qq(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>qq[i];
    }
    
    if (q == 1 && qq[1] == 1){
        ll S = 0;
        function<void(int, int)> dfs = [&](int v, int pr){
            for (auto [i, w1, w2]: g[v]){
                if (i == pr) continue;
                S += w2;
                dfs(i, v);
            }
        };
        dfs(1, 0);
        ll out = inf;
        function<void(int, int)> solve = [&](int v, int pr){
            out = min(out, tot - S);
            for (auto [i, w1, w2]: g[v]){
                if (i == pr) continue;
                S += (w1 - w2);
                solve(i, v);
                S -= (w1 - w2);
            }
        };
        solve(1, 0);
        cout<<out<<"\n";
        return 0;
    }
    if (q == 1 && qq[1] == 2){
        vector<ll> d(n + 1);
        vector<int> tin(n + 1), tout(n + 1);
        ll S = 0;
        int timer = 0;
        function<void(int, int)> dfs = [&](int v, int pr){
            tin[v] = ++timer;
            for (auto [i, w1, w2]: g[v]){
                if (i == pr) continue;
                S += w2;
                d[i] = d[v] + w1;
                dfs(i, v);
            }
            tout[v] = timer;
        };
        dfs(1, 0);
        
        ST T(n);
        for (int i = 1; i <= n; i++) T.upd(tin[i], d[i]);
        T.build();
        
        ll out = inf;
        function<void(int, int)> solve = [&](int v, int pr){
            out = min(out, tot - (S + T.get().ff));
            for (auto [i, w1, w2]: g[v]){
                if (i == pr) continue;
                S += (w1 - w2);
                T.add(1, n, w2);
                T.add(tin[i], tout[i], -(w1 + w2));
                solve(i, v);
                S -= (w1 - w2);
                T.add(1, n, -w2);
                T.add(tin[i], tout[i], (w1 + w2));
            }
        };
        solve(1, 0);
        
        cout<<out<<"\n";
        return 0;
    }
        
    vector<int> tin(n + 1), tout(n + 1), inv(n + 1), p(n + 1), dd(n + 1);
    vector<ll> d(n + 1);
    int timer = 0; ll S = 0;
    function<void(int, int)> dfs = [&](int v, int pr){
        p[v] = pr;
        tin[v] = ++timer;
        for (auto [i, w1, w2]: g[v]){
            if (i == pr) continue;
            S += w2;
            dd[i] = w1;
            d[i] = d[v] + w1;
            dfs(i, v);
        }
        tout[v] = timer;
    };
    
    vector<ll> out(n + 1, inf);
    vector<bool> used(n + 1);
    ST T(n);
    for (int i = 1; i <= n; i++){
        S = d[i] = dd[i] = timer = 0;
        dfs(i, 0);
        out[1] = min(out[1], tot - S);
        for (int j = 1; j <= n; j++){
            T.upd(tin[j], d[j]);
            inv[tin[j]] = j;
        }
        T.build();
        fill(used.begin(), used.end(), 0);
        used[i] = 1;
        for (int j = 2; j <= n; j++){
            auto [x, y] = T.get();
            if (!x) continue;
            int v = inv[y];
            while (!used[v]){
                T.add(tin[v], tout[v], -dd[v]);
                used[v] = 1;
                v = p[v];
            }
            S += x;
            out[j] = min(out[j], tot - S);
        }
    }
    for (int i = 1; i <= n; i++) out[i] = min(out[i], out[i - 1]);
    
    for (int i = 1; i <= q; i++){
        cout<<out[qq[i]]<<"\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44