Submission #1302947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302947		SzymonKrzywda	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	339 ms	89272 KiB

designated_cities

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;

const ll MAXN = 2e5 + 7;

vector<int> graf[MAXN];
ll koszt[MAXN][2];
bool wziete[MAXN];
int parent[MAXN];
ll ans[MAXN];
ll dp[MAXN];
int pre[MAXN][2];

int root = 1, aktpre = 0;


void dfs(int v, int p) {
    pre[v][0] = aktpre++;
    parent[v] = p;
    for (int s : graf[v]) {
        if (s != p) dfs(s, v);
    }
    pre[v][1] = aktpre++;
}


ll dfs2(int v, int p) {
    for (int s : graf[v]) {
        if (s != p) {
            //cout << v << ' ' << dp[v] << ' ' << s << ' ' << koszt[s][1] << '\n';
            dp[v] = max(dp[v], dfs2(s, v) + koszt[s][1]);
        }
    }
    return dp[v];
}

void dfs3(int v, int p, ll maxrodzic, ll suma1) {
    ans[1] = max(ans[1], suma1);
   // cout << "OH: " << v << ' ' << dp[v] << ' ' << maxrodzic << ' ' << suma1 << '\n';

    if (suma1 + max(maxrodzic, dp[v]) > ans[2]) {
        ans[2] = suma1 + max(maxrodzic, dp[v]);
        root = v;
    }


    multiset<ll, greater<ll>> secik;

    for (int s : graf[v]) {
        if (s != p){
            secik.insert(dp[s] + koszt[s][1]);
        }
    }
    // cout << "U: ";
    // for (int val : secik) cout << val <<  ' ';
    // cout << '\n';

    for (int s : graf[v]) {
        if (s == p) continue;
        //cout << *secik.begin() << ' ' << dp[s] + koszt[s][1] << ' ' << max(maxrodzic, *(++secik.begin())) << '\n';
        if (*(secik.begin()) == dp[s] + koszt[s][1]) {
            if (secik.size() > 1) dfs3(s, v, max(maxrodzic, *(++secik.begin())) + koszt[s][0], suma1 -koszt[s][0] + koszt[s][1]);
            else dfs3(s, v, maxrodzic + koszt[s][0], suma1 - koszt[s][0] + koszt[s][1]);
        }
        else dfs3(s, v, max(maxrodzic, *secik.begin()) + koszt[s][0], suma1 - koszt[s][0] + koszt[s][1]);
    }
}


const int base = 1 << 19;
ll tree[2 * base][2]; //{v, max}
ll lazy[2 * base]; //{v, max}

void push_l(int v) {
    tree[v * 2][1] += lazy[v];
    tree[v * 2 + 1][1] += lazy[v];
    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
}

void edit(int v, int vl, int vr, int l, int r, ll val) {
    if (vl > r || vr < l) return;
    if (l <= vl && vr <= r) {
        tree[v][1] += val;
        lazy[v] += val;
        return;
    }
    push_l(v);
    edit(v * 2, vl, (vl + vr) /2 , l, r, val);
    edit(v * 2 + 1, (vl + vr) / 2 + 1, vr , l, r, val);
    if (tree[v * 2][1] > tree[v * 2 + 1][1]) {
        tree[v][0] = tree[v * 2][0];
    }
    else tree[v][0] = tree[v * 2 + 1][0];

    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
}

void build(int v) {
    if (v >= base) return;
    build(v * 2);
    build(v * 2 + 1);
    if (tree[v * 2][1] > tree[v * 2 + 1][1]) {
        tree[v][0] = tree[v * 2][0];
    }
    else tree[v][0] = tree[v * 2 + 1][0];

    tree[v][1] = max(tree[v * 2][1], tree[v * 2 + 1][1]);
}


void dfs4(int v, int p, ll aktcost) {
    tree[base + pre[v][0]][1] = aktcost;
    tree[base + pre[v][0]][0] = v;
    for (int s : graf[v]) {
        if (s != p) dfs4(s, v, aktcost + koszt[s][1]);
    }
}





int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, a, b, c , d;
    cin >> n;
    vector<pair<pair<ll, ll>, pair<ll, ll>>> kr;

    for (ll i = 0; i < n - 1; i++) {
        cin >> a >> b >> c >> d;
        graf[a].push_back(b);
        graf[b].push_back(a);
        kr.push_back({{a, b}, {c, d}});
    }

    ll aktkoszt = 0;
    
    dfs(1, 1);

    for (auto & k : kr) {
        if (parent[k.first.second] == k.first.first) {
            swap(k.first.second, k.first.first);
            swap(k.second.first, k.second.second);
        }
        //cout << k.first.first << ' ' << k.first.second << ' ' << k.second.first << ' ' << k.second.second << '\n';
        koszt[k.first.first][0] = k.second.first;
        koszt[k.first.first][1] = k.second.second;
        aktkoszt += k.second.first;
    }

    // for (int i = 1; i <= n; i++ ) {
    //     cout << i << ": " << koszt[i][0] << ' ' << koszt[i][1] << '\n';
    // }

    dfs2(1, 1);
    dfs3(1, 1, 0, aktkoszt);

    aktpre = 0;
    dfs(root, root);
    aktkoszt = 0;

    for (int i = 0; i < MAXN; i++) {
        koszt[i][0] = 0;
        koszt[i][1] = 0;
    }

    for (auto & k : kr) {
        if (parent[k.first.second] == k.first.first) {
            swap(k.first.second, k.first.first);
            swap(k.second.first, k.second.second);
        }
        //cout << k.first.first << ' ' << k.first.second << ' ' << k.second.first << ' ' << k.second.second << '\n';
        koszt[k.first.first][0] = k.second.first;
        koszt[k.first.first][1] = k.second.second;
        aktkoszt += k.second.first;
    }


    ll suma = 0;
    for (int i = 1; i <= n; i++) suma += koszt[i][0] + koszt[i][1];

    dfs4(root, root, 0);
    int licznik = 2;
    wziete[root] = 1;

    build(1);

    while (aktkoszt < suma) {
        int v = tree[1][0];
        aktkoszt += tree[1][1];
        //cout << v << ' ' << tree[1][1] << '\n';

        while (!wziete[v]) {
            edit(1, 0, base - 1, pre[v][0], pre[v][1], -koszt[v][1]);
            wziete[v] = 1;
            v = parent[v];
        }

        ans[licznik++] = aktkoszt;

    }


    for (int i = 1; i <= n; i++) ans[i] = max(ans[i - 1], ans[i]);







    //for (int i = 1; i <= n; i++) cout << suma - ans[i] << ' ';

    int q, val;
    cin >> q;
    while (q--) {
        cin >> val;
        cout << suma - ans[val] << '\n';
    }





    return 0;
}

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