Submission #1207837

#TimeUsernameProblemLanguageResultExecution timeMemory
1207837Zbyszek99Fireworks (APIO16_fireworks)C++20
26 / 100
9 ms19468 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define vi vector<int> #define vl vector<long long> #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll rand(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct dp { priority_queue<ll> points; ll init_slope = 0; void merge(dp other) { init_slope += other.init_slope; while(!other.points.empty()) { points.push(other.points.top()); other.points.pop(); } } void add_edge(ll x) { ll cur_slope = init_slope + siz(points); ll opt_poz = 0; ll prev = 0; while(true) { ll cur = points.top(); prev = opt_poz; opt_poz = cur; cur_slope--; // cout << opt_poz << " " << cur_slope << " slope\n"; points.pop(); if(cur_slope == -1) { break; } } points.push(opt_poz+x); points.push(prev+x); } }; vi graph[300'001]; ll edge[300'001]; dp ansdp[300001]; void dfs(int v) { if(siz(graph[v]) == 0) { ansdp[v].init_slope = -1; ansdp[v].points.push(edge[v]); ansdp[v].points.push(edge[v]); } else { bool was = 0; forall(it,graph[v]) { dfs(it); if(!was) { was = 1; ansdp[v] = ansdp[it]; } else { if(siz(ansdp[it].points) > siz(ansdp[v].points)) { swap(ansdp[v],ansdp[it]); } ansdp[v].merge(ansdp[it]); } } if(v != 1) ansdp[v].add_edge(edge[v]); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random(); int n,m; cin >> n >> m; ll cur_ans = 0; rep2(i,2,n+m) { int p; cin >> p >> edge[i]; cur_ans += edge[i]; graph[p].pb(i); } dfs(1); ll ans_ = cur_ans; ll cur_slope = ansdp[1].init_slope; ll prev_point = 0; vi p; while(!ansdp[1].points.empty()) { p.pb(ansdp[1].points.top()); ansdp[1].points.pop(); } reverse(all(p)); forall(it,p) { cur_ans += cur_slope * (it-prev_point); prev_point = it; cur_slope++; ans_ = min(ans_,cur_ans); } cout << 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...