Submission #413031

#	Time	Username	Problem	Language	Result	Execution time	Memory
413031		phathnv	Road Closures (APIO21_roads)	C++11	100 / 100	457 ms	52348 KiB

roads

#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

const int N = 1e5;

int k, deg[N];
long long dp[N][2], sum[N], f[N];
multiset<long long> s[N][2];
vector<pair<int, int>> preAdj[N], adj[N];
bool mark[N];
set<int> cur, needVisit;

void Add(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] += val0;
    f[u] += val1 - val0;
    s[u][0].insert(val1 - val0);
}

void Del(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] -= val0;
    if (s[u][0].find(val1 - val0) != s[u][0].end()) {
        f[u] -= val1 - val0;
        s[u][0].erase(s[u][0].find(val1 - val0));
    } else {
        s[u][1].erase(s[u][1].find(val1 - val0));
    }
}

void Fix(int u, int sz) {
    while((int) s[u][0].size() > sz) {
        long long x = *s[u][0].rbegin();
        f[u] -= x;
        s[u][0].erase(s[u][0].find(x));
        s[u][1].insert(x);
    }
    while((int) s[u][0].size() < sz && !s[u][1].empty()) {
        long long x = *s[u][1].begin();
        f[u] += x;
        s[u][1].erase(s[u][1].find(x));
        s[u][0].insert(x);
    }
    while(!s[u][0].empty() && !s[u][1].empty()) {
        if (*s[u][0].rbegin() > *s[u][1].begin()) {
            long long a = *s[u][0].rbegin();
            long long b = *s[u][1].begin();
            f[u] += b - a;
            s[u][0].erase(s[u][0].find(a));
            s[u][1].erase(s[u][1].find(b));
            s[u][0].insert(b);
            s[u][1].insert(a);
        } else {
            break;
        }
    }
}

void Dfs(int u, int p) {
    needVisit.erase(u);
    vector<pair<long long, long long>> vals;
    for(auto e : adj[u]) {
        int v = e.first;
        int w = e.second;
        if (v == p)
            continue;
        Dfs(v, u);
        vals.push_back({dp[v][1] + w, dp[v][0]});
    }
    for(auto p : vals)
        Add(u, p.first, p.second);
    Fix(u, k);
    dp[u][1] = sum[u] + f[u];
    dp[u][0] = sum[u] + (f[u] - *s[u][0].rbegin());
    for(auto p : vals)
        Del(u, p.first, p.second);

}

vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
    k = n;
    vector<int> ord(n);
    for(int i = 0; i < n - 1; i++) {
        deg[u[i]]++;
        deg[v[i]]++;
        Add(u[i], w[i], 0);
        Add(v[i], w[i], 0);
        preAdj[u[i]].push_back({v[i], w[i]});
        preAdj[v[i]].push_back({u[i], w[i]});
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](const int &u, const int &v) {
        return deg[u] > deg[v];
    });
    vector<long long> res(n, 0);
    int ptr = 0;
    for(k = n - 1; k >= 1; k--) {
        while(ptr < n && deg[ord[ptr]] > k) {
            int u = ord[ptr++];
            cur.insert(u);
            mark[u] = 1;
            for(auto e : preAdj[u]) {
                int v = e.first;
                int w = e.second;
                if (!mark[v])
                    continue;
                Del(u, w, 0);
                Del(v, w, 0);
                adj[u].push_back({v, w});
                adj[v].push_back({u, w});
            }
        }
        needVisit = cur;
        while(!needVisit.empty()){
            int u = *needVisit.begin();
            Dfs(u, -1);
            res[k] += dp[u][1];
        }
    }
    res[0] = accumulate(w.begin(), w.end(), 0ll);

    return res;
}

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