Submission #1009751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009751		Cookie	Road Closures (APIO21_roads)	C++14	100 / 100	263 ms	71224 KiB

roads

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
//#define int long long
typedef unsigned long long ull;
//const int x[4] = {0, 0, 1, -1};
//const int y[4] = {1, -1, 0, 0};
const int mxn = 2e5 + 5;
const ll mod = 998244353, mod2 = 1e9 + 1977, inf = 1e14 + 5;
vt<ll>cc[mxn + 1];
struct BIT{
    vt<ll>bit;
    void init(int siz){
        bit.resize(siz + 3, 0);
    }
    void upd(int p, ll v){
        while(p < sz(bit)){
            bit[p] += v; p += p & (-p);
        }
    }
    ll get(int p){
        ll ans = 0;
        while(p){
            ans += bit[p]; p &= p -= p & (-p);
        }
        return(ans);
    }
    int kth(int k){
        if(get(sz(bit) - 1) < k)return(-1);
        int pos = 0, sm = 0;
        for(int i = 17; i >= 0; i--){
            if(pos + (1 << i) < sz(bit) && sm + bit[pos + (1 << i)] < k){
                sm += bit[pos + (1 << i)]; pos += (1 << i);
            }
        }
        return(pos + 1);
    }
};
int find(int node, int v){
    return(lower_bound(ALL(cc[node]), v) - cc[node].begin() + 1);
}
BIT tot[mxn + 1], cnt[mxn + 1];
struct E{
    int u, v, w;
};
vt<E>edge[mxn + 1];
vt<int>node[mxn + 1];
int n;
int deg[mxn + 1];
vt<pll>adj[mxn + 1];
vt<ll>ans;
bool vis[mxn + 1];
ll dp[mxn + 1][2];
ll kth(int node, ll k){
    if(k <= 0)return(0);
    int v = cnt[node].kth(k);
    if(v == -1)return(inf);
    ll ans = tot[node].get(v - 1) + (k - cnt[node].get(v - 1)) * cc[node][v - 1];
    return(ans);
}
void dfs(int s, int need){
    vis[s] = 1;
    ll tot = 0;
    vt<ll>comp;
    for(auto [i, w]: adj[s]){
        if(!vis[i]){
            dfs(i, need); dp[i][0] = min(dp[i][0], dp[i][1] + w);
            comp.pb(dp[i][1] + w - dp[i][0]); tot += dp[i][0];
        }
    }
    sort(ALL(comp));
    dp[s][0] = dp[s][1] = inf;
    for(int i = 0; i <= sz(comp); i++){
        dp[s][0] = min(dp[s][0], kth(s, deg[s] - need - i) + tot);
        dp[s][1] = min(dp[s][1], kth(s, deg[s] - 1 - need - i) + tot);
        if(i < sz(comp))tot += comp[i];
    }
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n = N;
    bool ok = 1;
    ans.resize(n, 0);
    for(int i = 0; i < n - 1; i++){
        U[i]++; V[i]++;
        ok &= (U[i] == 1);
         deg[U[i]]++; deg[V[i]]++; cc[U[i]].pb(W[i]); cc[V[i]].pb(W[i]);
    }
    for(int i = 1; i <= n; i++){
        sort(ALL(cc[i])); cc[i].resize(unique(ALL(cc[i])) - cc[i].begin());
        tot[i].init(sz(cc[i])); cnt[i].init(sz(cc[i]));
    }
    for(int i= 0; i < n - 1; i++){
        tot[U[i]].upd(find(U[i], W[i]), W[i]); tot[V[i]].upd(find(V[i], W[i]), W[i]); 
        cnt[U[i]].upd(find(U[i], W[i]), 1); cnt[V[i]].upd(find(V[i], W[i]), 1); 
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < deg[i]; j++){
            node[j].pb(i);
        }
    }
    for(int i = 0; i < n - 1; i++){
        for(int j = min(deg[U[i]], deg[V[i]]) - 1; j >= 0; j--){
            edge[j].pb({U[i], V[i], W[i]}); 
        }
    }
    for(int i = 0; i < n; i++){
        for(auto [u, v, w]: edge[i]){
            //cout << i << " " << u << " " << v << " " << w << "\n";
            tot[u].upd(find(u, w), -w); cnt[u].upd(find(u, w), -1); 
            tot[v].upd(find(v, w), -w); cnt[v].upd(find(v, w), -1);
            adj[u].pb(mpp(v, w)); adj[v].pb(mpp(u, w)); 
        }
        for(auto u: node[i]){
            if(vis[u] == 0){
                dfs(u, i); 
                ans[i] += dp[u][0];
            }
        }
        for(auto u: node[i]){
            adj[u].clear(); vis[u] = 0;
        }
        for(auto [u, v, w]: edge[i]){
            //cout << i << " " << u << " " << v << " " << w << "\n";
            tot[u].upd(find(u, w), w); cnt[u].upd(find(u, w), 1); 
            tot[v].upd(find(v, w), w); cnt[v].upd(find(v, w), 1);
        }
    }
    return(ans);
}
/*
int main() {
  int N;
  assert(1 == scanf("%d", &N));
 
  std::vector<int> U(N - 1), V(N - 1), W(N - 1);
  for (int i = 0; i < N - 1; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }
 
  std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
  for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
    if (i > 0) {
      printf(" ");
    }
    printf("%lld",closure_costs[i]);
  }
  printf("\n");
  return 0;
}
*/

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, int)':
roads.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto [i, w]: adj[s]){
      |              ^
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:124:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |         for(auto [u, v, w]: edge[i]){
      |                  ^
roads.cpp:139:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |         for(auto [u, v, w]: edge[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