Submission #740952

#	Time	Username	Problem	Language	Result	Execution time	Memory
740952		becaido	Road Closures (APIO21_roads)	C++17	100 / 100	202 ms	53136 KiB

roads

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "roads.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2.5e5 + 5;

int n;
bool vs[SIZE];
int m, a[SIZE], sz[SIZE];
vector<pair<int, int>> adj[SIZE];

struct DS {
    multiset<ll> lms, rms;
    ll sum;
    void add(ll x) {
        if (lms.size() == 0 || x >= *lms.rbegin()) rms.insert(x);
        else lms.insert(x), sum += x;
    }
    void del(ll x) {
        if (lms.count(x)) lms.erase(lms.find(x)), sum -= x;
        else rms.erase(rms.find(x));
    }
    ll cal(int k) {
        k = (int) (lms.size() + rms.size()) - k;
        k = max(k, 0);
        while (lms.size() > k && *lms.rbegin() > 0) {
            sum -= *lms.rbegin();
            rms.insert(*lms.rbegin());
            lms.erase(prev(lms.end()));
        }
        while (lms.size() < k || (rms.size() && *rms.begin() < 0)) {
            sum += *rms.begin();
            lms.insert(*rms.begin());
            rms.erase(rms.begin());
        }
        return sum;
    }
} ds[SIZE];

ll cal(int k) {
    FOR (i, 1, m) vs[a[i]] = 0;
    while (m >= 1 && sz[a[m]] <= k) m--;
    ll sum = 0;
    auto dfs = [&](auto dfs, int pos, int fa)->pair<ll, ll> {
        vs[pos] = 1;
        while (adj[pos].size() && sz[adj[pos].back().F] <= k) {
            ds[pos].add(adj[pos].back().S);
            adj[pos].pop_back();
        }
        vector<ll> v;
        ll sum1 = 0, sum2 = 0;
        for (auto [np, w] : adj[pos]) if (np != fa) {
            auto [v1, v2] = dfs(dfs, np, pos);
            sum1 += v2;
            ds[pos].add(w + v1 - v2);
            v.pb(w + v1 - v2);
        }
        sum2 = sum1;
        sum1 += ds[pos].cal(k);
        sum2 += ds[pos].cal(k - 1);
        for (ll x : v) ds[pos].del(x);
        return {sum1, sum2};
    };
    FOR (i, 1, m) if (!vs[a[i]]) sum += dfs(dfs, a[i], a[i]).F;
    return sum;
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    vector<ll> ans;
    n = N;
    ll wsum = 0;
    FOR (i, 0, n - 2) {
        int a = U[i] + 1, b = V[i] + 1, w = W[i];
        adj[a].pb(b, w);
        adj[b].pb(a, w);
        wsum += w;
    }
    ans.pb(wsum);
    FOR (i, 1, n) sz[i] = adj[i].size();
    FOR (i, 1, n) sort(adj[i].begin(), adj[i].end(), [](auto lhs, auto rhs) {
        return sz[lhs.F] > sz[rhs.F];
    });
    m = n;
    iota(a + 1, a + n + 1, 1);
    sort(a + 1, a + n + 1, [](int lhs, int rhs) {
        return sz[lhs] > sz[rhs];
    });
    FOR (i, 1, n - 1) ans.pb(cal(i));
    return ans;
}

Compilation message (stderr)

roads.cpp: In member function 'long long int DS::cal(int)':
roads.cpp:47:27: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         while (lms.size() > k && *lms.rbegin() > 0) {
      |                ~~~~~~~~~~~^~~
roads.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         while (lms.size() < k || (rms.size() && *rms.begin() < 0)) {
      |                ~~~~~~~~~~~^~~

• 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