Submission #791382

#	Time	Username	Problem	Language	Result	Execution time	Memory
791382		nguyentunglam	Road Closures (APIO21_roads)	C++17	100 / 100	284 ms	145792 KiB

roads

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 1e5 + 10, M = 30;
vector<pair<int, int> > adj[N];
vector<long long> f[N], g[N], h[N];
long long cost;
int cnt;

struct node {
    node * child[2];
    int cnt;
    long long sum;
    node () {
        child[0] = child[1] = nullptr;
        cnt = sum = 0;
    }
};

node * root = new node();

void add(long long val, int type) {
    if (val < 0) {
        cost += val * type;
        cnt += type;
        return;
    }
    node * p = root;
    for(int j = M; j >= 0; j--) {
        bool x = val >> j & 1;
        if (!p -> child[x]) p -> child[x] = new node();
        p = p -> child[x];
        p -> sum += val * type; p -> cnt += type;
    }
}

long long get(int k) {
    node * p = root;
    long long ret = 0;
    for(int j = M; j >= 0; j--) {
        if (p -> child[0] && k < p -> child[0] -> cnt) p = p -> child[0];
        else {
            if (p -> child[0]) {
                k -= p -> child[0] -> cnt;
                ret += p -> child[0] -> sum;
            }
            if (!p -> child[1]) return ret;
            p = p -> child[1];
        }
    }
    long long val = p -> sum / p -> cnt;
    return ret + k * val;
}

long long F(int v, int i) {
    if (g[v].size() <= i) exit(0);
    return f[v].size() <= i ? g[v][i] : f[v][i];
}

void dfs(int u, int p = 0) {
    if (adj[u].size() == 1 && u > 0) return;

    vector<pair<int, int>> child;

    for(auto &[v, w] : adj[u]) if (v != p) {
        dfs(v, u);
        child.emplace_back(v, w);
    }
    sort(all(child), [] (const ii &x, const ii &y) {
         return g[x.first].size() > g[y.first].size();
         });

    int head = child[0].first;
    swap(g[u], g[head]);

    for(int i = 0; i <= min((int) g[u].size() - 1, (int) child.size()); i++) {
        g[head].push_back(g[u][i]);
    }

    for(int i = 0; i < f[head].size(); i++) {
        if (i <= child.size()) g[u][i] = f[head][i];
        else g[u][i] = min(g[u][i] + child[0].second, f[head][i]);
    }

    for(auto &[v, w] : child) if (v != head) {
        for(int i = 0; i < g[v].size(); i++) {
            if (i <= child.size()) g[u][i] += F(v, i);
            else g[u][i] += min(g[v][i] + w, F(v, i));
        }
    }

    while (g[u].size() <= child.size()) g[u].push_back(0);
    f[u].resize(child.size() + 1);

    int j = child.size() - 1;
    for(int i = 0; i <= child.size(); i++) {
        while (j >= 0 && g[child[j].first].size() <= i) {
            add(child[j].second, 1);
            j--;
        }

        for(int k = 0; k <= j; k++) {
            int v, w; tie(v, w) = child[k];
            add(g[v][i] + w - F(v, i), 1);
        }

        long long tmp = g[u][i];
        g[u][i] = tmp + get(max(0, (int) child.size() - i - cnt)) + cost;
        if (i > 0) f[u][i] = tmp + get(max(0, (int) child.size() - i + 1 - cnt)) + cost;
        else f[u][i] = g[u][i];

        g[u][i] = min(g[u][i], f[u][i]);

        for(int k = 0; k <= j; k++) {
            int v, w; tie(v, w) = child[k];
            add(g[v][i] + w - F(v, i), - 1);
        }
    }
    j++;
    while (j < child.size()) add(child[j].second, -1), j++;
}

vector<long long> minimum_closure_costs (int n, vector<int> u, vector<int> v, vector<int> w) {
    for(int i = 0; i < n - 1; i++) {
        adj[u[i]].emplace_back(v[i], w[i]);
        adj[v[i]].emplace_back(u[i], w[i]);
    }
    dfs(0, 0);
    vector<long long> ret(n);
    for(int i = 0; i < g[0].size(); i++) {
        ret[i] = g[0][i];
    }
    return ret;
}

#ifdef ngu
int main() {
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }


    int n; cin >> n;
    vector<int> u(n), v(n), w(n);
    for(int i = 0; i < n; i++) cin >> u[i] >> v[i] >> w[i];
    vector<long long> res = minimum_closure_costs(n, u, v, w);
//    for(long long &j : res) cout << j << endl;
}
#endif // ngu

Compilation message (stderr)

roads.cpp: In function 'long long int F(int, int)':
roads.cpp:60:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     if (g[v].size() <= i) exit(0);
      |         ~~~~~~~~~~~~^~~~
roads.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     return f[v].size() <= i ? g[v][i] : f[v][i];
      |            ~~~~~~~~~~~~^~~~
roads.cpp: In function 'void dfs(int, int)':
roads.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 0; i < f[head].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
roads.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if (i <= child.size()) g[u][i] = f[head][i];
      |             ~~^~~~~~~~~~~~~~~
roads.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i = 0; i < g[v].size(); i++) {
      |                        ~~^~~~~~~~~~~~~
roads.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             if (i <= child.size()) g[u][i] += F(v, i);
      |                 ~~^~~~~~~~~~~~~~~
roads.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i = 0; i <= child.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
roads.cpp:101:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         while (j >= 0 && g[child[j].first].size() <= i) {
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
roads.cpp:124:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     while (j < child.size()) add(child[j].second, -1), j++;
      |            ~~^~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i = 0; i < g[0].size(); i++) {
      |                    ~~^~~~~~~~~~~~~

• 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