Submission #532055

#	Time	Username	Problem	Language	Result	Execution time	Memory
532055		fivefourthreeone	Road Closures (APIO21_roads)	C++17	100 / 100	170 ms	50876 KiB

roads

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl

using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 250005;
struct BIT {
    int N;
    vector<ll> arr;
    vector<ll> cnt;
    void init(int n) {
        N = n;
        arr.resize(N+1, 0);
        cnt.resize(N+1, 0);
    }
    void upd(int p, int x) {
        p++;
        while(p <= N) {
            arr[p] += x;
            cnt[p]++;
            p += p&-p;
        }
    }
    ll qsum(int p) {
        ll res = 0;
        p++;
        while(p > 0) {
            res += arr[p];
            p -= p&-p;
        }
        return res;
    }
    int search (int v) {
        int sum = 0;
        int pos = 0;
	    for(int i=17; i>=0; i--) {
		    if(pos + (1 << i) < N && sum + cnt[pos + (1 << i)] < v) {
			    sum += cnt[pos + (1 << i)];
			    pos += (1 << i);
		    }
	    }
	    return pos;
    }
    ll gethighest(int k) {
        //cout << k << " " << N << " higher?" << endl;
        if (k == 0)return 0;
        int pos = search(k);
        return qsum(pos);
    }
}bit[mxN];
vector<array<int, 3>> adj[mxN];
int deg[mxN];
bool done[mxN];
vector<int> here;
ll dp[mxN][2]; //dp[0] is cant use, dp[1] is can use
vector<int> all;
ll die[mxN];
ll dfs(int u, int p, int k) {
    if (done[u]) return -1;
    //cout << u << " in" << endl;
    here.push_back(u);
    done[u] = 1;
    vector<ll> compute;
    ll always = 0;
    for (int _ = 0; _ < adj[u].size(); _++) {
        int v = adj[u][_][0];
        ll w = adj[u][_][1];
        int pos = adj[u][_][2];
        if (v == p)continue;
        if (deg[v] == k) {
            //cout << u << " " << v << " " << pos << " " << w << " bit update\n";
            bit[u].upd(pos, w);
            continue;
        } else if (deg[v] < k) break;
        dfs(v, u, k);
        always += dp[v][0];
        if (dp[v][1] + w - dp[v][0] > 0) {
            compute.senpai(dp[v][1] + w - dp[v][0]);   
        }
    }
    sort(compute.rbegin(), compute.rend());
    dp[u][0] = bit[u].gethighest(k);
    dp[u][1] = bit[u].gethighest(k-1);
    ll curr = 0;
    for (int i = 0; i < compute.size(); i++) {
        //cout << i << " " << compute[i] << "\n";
        curr += compute[i];
        if (k-i-1 >= 0) dp[u][0] = max(dp[u][0], curr + bit[u].gethighest(k-i-1));
        if (k-i-2 >= 0) dp[u][1] = max(dp[u][1], curr + bit[u].gethighest(k-i-2));
    }
    dp[u][0] += always;
    dp[u][1] += always;
    //cout << u << " out " << dp[u][0] << " " << dp[u][1] << endl;
    return dp[u][0];
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
    all.resize(n);
    iota(all.begin(), all.end(), 0);
    ll tot = 0;
    for (int i = 0; i < n-1; i++) {
        adj[u[i]].senpai({v[i], w[i], 0});
        adj[v[i]].senpai({u[i], w[i], 0});
        deg[u[i]]++;
        deg[v[i]]++;
        tot += w[i];
    }
    for (int i = 0; i < n-1; i++) {
        die[max(deg[u[i]], deg[v[i]])] += w[i];
    }
    for (int i = 1; i < n; i++) {
        die[i] += die[i-1];
    }
    owo(i, 0, n) {
        sort(adj[i].begin(), adj[i].end(), [&](array<int, 3> a, array<int, 3> b) {
            return a[1] > b[1]; 
        });
        for (int j = 0; j < adj[i].size(); j++) {
            adj[i][j][2] = j;
        }
        sort(adj[i].begin(), adj[i].end(), [&](array<int, 3> a, array<int, 3> b) {
            return deg[a[0]] > deg[b[0]]; 
        });
        bit[i].init(deg[i]);
    }
    sort(all.begin(), all.end(), [&](int a, int b) {
        return deg[a] > deg[b];
    });
    vector<ll> res(n);
    for (int k = 1; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (deg[all[i]] <= k)break;
            if (!done[all[i]]) {
                res[k] += dfs(all[i], -1, k);
            }
        }
        res[k] += die[k];
        for (int u : here) {
            done[u] = false;
        }
        here.clear();
    }
    owo(i, 0, n) {
        res[i] = tot - res[i];
    }
    return res;
}

Compilation message (stderr)

roads.cpp: In function 'll dfs(int, int, int)':
roads.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int _ = 0; _ < adj[u].size(); _++) {
      |                     ~~^~~~~~~~~~~~~~~
roads.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < compute.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int j = 0; j < adj[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

• 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