제출 #975404

#제출 시각아이디문제언어결과실행 시간메모리
975404Tuanlinh123도로 폐쇄 (APIO21_roads)C++17
0 / 100
200 ms79044 KiB
// #include "grader.cpp" #include "roads.h" #include<bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=100005, inf=1e17; struct SegTree { ll n; vector <ll> val, cnt, sum; void init(vector <ll> &v) { val=v, n=sz(val); cnt.assign(n*4+1, 0), sum.assign(n*4+1, 0); } void update(ll i, ll Start, ll End, ll idx, ll v) { if (Start==End) return cnt[i]+=v, sum[i]+=val[idx]*v, void(); ll mid=(Start+End)/2; if (mid<=idx) update(i*2, Start, mid, idx, v); else update(i*2+1, mid+1, End, idx, v); cnt[i]=cnt[i*2]+cnt[i*2+1], sum[i]=sum[i*2]+sum[i*2+1]; } void add(ll x) {update(1, 0, n-1, lower_bound(val.begin(), val.end(), x)-val.begin(), 1);} void sub(ll x) {update(1, 0, n-1, lower_bound(val.begin(), val.end(), x)-val.begin(), -1);} ll Sum(ll i, ll Start, ll End, ll k) { if (Start==End) { if (cnt[i]<k) return inf; return val[Start]*k; } ll mid=(Start+End)/2; if (cnt[i*2]>=k) return Sum(i*2, Start, mid, k); return min(inf, sum[i*2]+Sum(i*2+1, mid+1, End, k-cnt[i*2])); } ll Sum(ll k) {return Sum(1, 0, n-1, k);} ll Find(ll i, ll Start, ll End, ll k) { if (Start==End) { if (cnt[i]<k) return inf; return val[Start]; } ll mid=(Start+End)/2; if (cnt[i*2]>=k) return Find(i*2, Start, mid, k); return Find(i*2+1, mid+1, End, k-cnt[i*2]); } ll Find(ll k) {return Find(1, 0, n-1, k);} }; vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W) { vector <vector <pll>> A(n), At(n); for (ll i=0; i<sz(W); i++) A[U[i]].pb({V[i], W[i]}), A[V[i]].pb({U[i], W[i]}); vector <SegTree> S(n); vector <vector <ll>> H(n); for (ll i=0; i<n; i++) { vector <ll> num; for (auto [v, w]:A[i]) num.pb(w); sort(num.begin(), num.end()); num.resize(unique(num.begin(), num.end())-num.begin()); H[sz(A[i])-1].pb(i), S[i].init(num); for (ll j:num) S[i].add(j); } vector <ll> cr, check(n, 0), answer(n, 0); vector <array<ll, 2>> dp(n); for (ll i=n-1; i>=0; i--) { for (ll u:H[i]) { for (auto [v, w]:A[u]) At[v].pb({u, w}), S[v].sub(w); cr.pb(u); } function <void(ll, ll, ll )> dfs=[&](ll u, ll wpa, ll pa) { check[u]=1, dp[u][0]=0, dp[u][1]=wpa; for (ll j=0; j<2; j++) { vector <ll> num; ll cnt=sz(A[u])-i-j; for (auto [v, w]:At[u]) { if (v==pa) continue; if (!check[v]) dfs(v, w, u); dp[u][j]+=dp[v][0]; if (dp[v][1]<dp[v][0]) dp[u][j]+=dp[v][1]-dp[v][0], cnt--; else num.pb(dp[v][1]-dp[v][0]); } if (cnt<=0) continue; dp[u][j]+=S[u].Sum(cnt); sort(num.begin(), num.end()); for (ll i=0; i<sz(num) && cnt; i++) { if (num[i]<S[u].Find(cnt)) dp[u][j]+=num[i]+S[u].Sum(cnt-1)-S[u].Sum(cnt), cnt--; else break; } } }; for (ll u:cr) if (!check[u]) dfs(u, 0, u), answer[i]+=dp[u][0]; for (ll u:cr) check[u]=0; } return answer; }
#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...