Submission #416602

#TimeUsernameProblemLanguageResultExecution timeMemory
416602dooweyRoad Closures (APIO21_roads)C++14
12 / 100
311 ms93468 KiB
#include <bits/stdc++.h> #include "roads.h" using namespace std; typedef long long ll; typedef pair<ll,ll> pii; #define fi first #define se second #define mp make_pair const int N = (int)1e5 + 10; vector<int> u, v, w; int n; vector<pii> T[N]; bool comp(pii i, pii j){ return w[i.se] < w[j.se]; } struct edge{ int nex; int oo; int weight; }; bool active[N]; vector<int> ad[N]; ll dp[N][2]; struct segment_tree{ vector<pii> TREE; int sz; void init(int nn){ sz = nn; TREE.resize(sz * 4 + 16); } void add(int node, int cl, int cr, int v, int cc, ll w){ if(cl == cr){ TREE[node].fi = w; TREE[node].se = cc; return; } int mid = (cl + cr) / 2; if(mid >= v) add(node * 2, cl, mid, v, cc, w); else add(node * 2 + 1, mid + 1, cr, v, cc, w); TREE[node].fi = TREE[node * 2].fi + TREE[node * 2 + 1].fi; TREE[node].se = TREE[node * 2].se + TREE[node * 2 + 1].se; } ll get(int node, int cl, int cr, int cnt){ if(cnt == 0) return 0; if(cl == cr){ return TREE[node].fi; } int mid = (cl + cr) / 2; if(TREE[node * 2].se >= cnt){ return get(node * 2, cl, mid, cnt); } else{ return get(node * 2 + 1, mid + 1, cr, cnt - TREE[node * 2].se) + TREE[node * 2].fi; } } }; vector<pii> F[N]; segment_tree lows[N]; int k; bool vis[N]; void dfs(int u, ll las){ vis[u]=true; int deg = T[u].size(); vector<ll> vals; ll total = 0; for(auto x : F[u]){ if(vis[x.fi]) continue; dfs(x.fi, x.se); total += dp[x.fi][1]; vals.push_back(dp[x.fi][0] - dp[x.fi][1]); } sort(vals.begin(), vals.end()); int need; ll ash; for(int r = 0; r <= vals.size(); r ++ ){ // take parent need = (deg - k) - 1 - r; ash = total + las; if(need > 0) ash += lows[u].get(1, 0, deg - 1, need); if(lows[u].TREE[1].se >= need) dp[u][0] = min(dp[u][0], ash); // dont take parent ash = total; need = (deg - k) - r; if(need > 0) ash += lows[u].get(1, 0, deg - 1, need); if(lows[u].TREE[1].se >= need) dp[u][1] = min(dp[u][1], ash); if(r < vals.size()) total += vals[r]; } } int L[N]; vector<ll> minimum_closure_costs(int _n, vector<int> _u,vector<int> _v, vector<int> _w) { n = _n; u = _u; v = _v; w = _w; for(int i = 0 ; i < n - 1; i ++ ){ T[u[i]].push_back(mp(v[i], i)); T[v[i]].push_back(mp(u[i], i)); } for(int i = 0 ; i < n; i ++ ){ ad[T[i].size()].push_back(i); } for(int i = 0 ; i < n; i ++ ){ sort(T[i].begin(), T[i].end(), comp); lows[i].init(T[i].size()); for(int j = 0 ; j < T[i].size(); j ++ ){ lows[i].add(1, 0, lows[i].sz - 1, j, 1, w[T[i][j].se]); } } vector<int> vse; vector<ll> outp(n); for(int i = n - 1; i >= 0 ; i -- ){ for(auto x : vse){ vis[x]=false; dp[x][0]=dp[x][1]=(ll)1e18; } k = i; for(auto x : vse){ if(!vis[x]){ dfs(x, 0); outp[i] += dp[x][1]; } } for(auto x : ad[i]){ active[x]=true; vse.push_back(x); for(int j = 0; j < T[x].size(); j ++ ){ if(active[T[x][j].fi]){ F[x].push_back(mp(T[x][j].fi, w[T[x][j].se])); F[T[x][j].fi].push_back(mp(x, w[T[x][j].se])); lows[T[x][j].se].add(1, 0, lows[x].sz - 1, L[T[x][j].se], 0, 0); lows[x].add(1, 0, lows[x].sz - 1, j, 0, 0); } else{ L[T[x][j].se] = j; } } } } return outp; }

Compilation message (stderr)

roads.cpp: In function 'void dfs(int, ll)':
roads.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int r = 0; r <= vals.size(); r ++ ){
      |                    ~~^~~~~~~~~~~~~~
roads.cpp:109:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if(r < vals.size())
      |            ~~^~~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j = 0 ; j < T[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~
roads.cpp:153:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for(int j = 0; j < T[x].size(); j ++ ){
      |                            ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...