제출 #970840

#제출 시각아이디문제언어결과실행 시간메모리
970840AlperenT_도로 폐쇄 (APIO21_roads)C++17
0 / 100
775 ms1048576 KiB
#include "roads.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #define pb push_back #define F first #define S second #define ld long double #define aint(a) a.begin(),a.end() #define pii pair <int,int> #define PII pair<pii , pii> #define ll long long #define sz(v) (int)v.size() #define rep(i , a , b) for(int i=a;i <= (b);i++) #define per(i , a , b) for(int i=a;i >= (b);i--) #define deb(x) cout <<#x << " : " << x << "\n" ; using namespace std ; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn = 1e6 , maxq = 32, inf = 1e15+10 , lg = 19 ,sq = 707 ,mod = 998244353 ; vector <pii> G[maxn] ; ll dp[maxn][2] , k; void dfs(int v , int W = 0 , int p = -1){ dp[v][0] = dp[v][1] = 0; int x = max(0ll,sz(G[v])-k) ; priority_queue <ll> pq ; for(auto [u,w] : G[v]){ if(u == p)continue ; dfs(u , w , v) ; if(dp[u][0] <= dp[u][1]){ dp[v][0] += dp[u][0] ; x=max(x-1 , 0) ; }else{ dp[v][0] += dp[u][1] ; pq.push((-dp[u][1] + dp[u][0])); while(sz(pq) > x)pq.pop(); } } dp[v][1] = dp[v][0] ; dp[v][0] += W ; if(x==0)return ; while(sz(pq) > x)pq.pop(); if(sz(pq) < x){ while(sz(pq)){ dp[v][0] += pq.top() ; pq.pop() ; } dp[v][1] = inf ; }else{ bool ok =0 ; while(sz(pq)){ ll z = pq.top() ;pq.pop() ; if(ok)dp[v][0] += z ; ok = 1; dp[v][1] += z; } } } vector<ll> ans ; void sl(int l , int r , ll a =-1 , ll b= -1){ if(a==-1){ k = l ;dfs(0); a =dp[0][1]; } if(b==-1){ k = r ;dfs(0); b =dp[0][1]; } if(a==b){ rep(i , a , b)ans.pb(a); }else{ int mid = (l+r)/2 ; sl(l , mid , a , -1); sl(mid+1,r,-1,b); } } vector<ll> minimum_closure_costs(int n, vector<int> U,vector<int> V,vector<int> W) { rep(i ,0 , n-2){ G[V[i]].pb({U[i] , W[i]}) ; G[U[i]].pb({V[i] , W[i]}) ; } sl(0 ,n-1); return ans ; }
#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...