Submission #711428

#	Time	Username	Problem	Language	Result	Execution time	Memory
711428		irmuun	Road Closures (APIO21_roads)	C++17	12 / 100	2064 ms	14356 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define PI 3.1415926535897932384626433
#define all(s) s.begin(),s.end() 
 
const ll mod=1000000007,mod1=998244353,INF=1e18,MAX=1e9;
 
vector<ll> minimum_closure_costs(int n,vector<int>U,vector<int>V,vector<int>W){
    int cnt=0;
    bool ok=true;
    for(ll i=0;i<n-1;i++){
        if(U[i]==0){
            cnt++;
        }
        if(U[i]!=i||V[i]!=i+1){
            ok=false;
        }
    }
    if(cnt==n-1){
        sort(all(W));
        ll cur=0;
        for(ll i=0;i<n;i++){
            cur+=W[i];
        }
        vector<ll>ans;
        for(ll i=n-1;i>=0;i--){
            cur-=W[i];
            ans.pb(cur);
        }
        return ans;
    }
    if(ok==true){
        vector<ll>ans(n,0);
        ll cur=0;
        for(int i=0;i<n-1;i++){
            cur+=W[i];
        }
        ans[0]=cur;
        ll dp[n+5];
        dp[0]=0;
        dp[1]=W[0];
        for(int i=2;i<n;i++){
            dp[i]=min(dp[i-1],dp[i-2])+W[i-1];
        }
        ans[1]=min(dp[n-1],dp[n-2]);
        return ans;
    }
    ll dp[n+5][2];
    vector<pair<ll,ll>>dv[n+5];
    for(ll i=0;i<n-1;i++){
        dv[U[i]].pb({V[i],W[i]});
        dv[V[i]].pb({U[i],W[i]});
    }
    ll curK;
    function <void(ll,ll)> dfs=[&](ll u,ll p){
        vector<ll>vec;
        dp[u][0]=0;
        dp[u][1]=0;
        for(auto [x,y]:dv[u]){
            if(x!=p){
                dfs(x,u);
                dp[x][0]+=y;
                vec.pb(x);
            }
        }
        sort(all(vec),[&](ll a,ll b){
            return dp[a][1]-dp[a][0]<dp[b][1]-dp[b][0];
        });
        dp[u][0]=0;
        dp[u][1]=0;
        for(ll x=0;auto ver:vec){
            if(x<curK){
                dp[ver][0]+=min(dp[ver][0],dp[ver][1]);
            }
            else{
                dp[ver][0]+=dp[ver][0];
            }
            if(x<curK-1){
                dp[u][1]+=min(dp[ver][0],dp[ver][1]);
            }
            else{
                dp[u][1]+=dp[ver][0];
            }
            x++;
        }
    };
    vector<ll>ans(n,0);
    for(ll k=0;k<n;k++){
        curK=k;
        dfs(0,-1);
        ans.pb(min(dp[0][0],dp[0][1]));
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In lambda function:
roads.cpp:76:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   76 |         for(ll x=0;auto ver:vec){
      |                    ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22