Submission #984902

#	Time	Username	Problem	Language	Result	Execution time	Memory
984902		boyliguanhan	Road Closures (APIO21_roads)	C++17	100 / 100	172 ms	66176 KiB

roads

#include "roads.h"
#include<bits/stdc++.h>
#define I signed
using namespace std;
#define int long long
#define M 1<<18
vector<pair<int,int>>adj[M];
int deg[M],vis[M],dp[M][2],rem[M];
struct hp{
    vector<int>v;
    void ins(int x){
        v.push_back(x);
        push_heap(v.begin(),v.end());
    }
    int top(){
        return v[0];
    }
    void pop(){
        pop_heap(v.begin(),v.end());
        v.pop_back();
    }
};
struct hp2{
    hp a,b;
    int sz,sum;
    void ins(int x){
        a.ins(x);
        sz++;
        sum+=x;
    }
    void del(int x){
        b.ins(x);
        sz--;
        sum-=x;
    }
    void inter(){
        while(b.v.size()&&a.top()==b.top())
            a.pop(),b.pop();
    }
    int top(){
        inter();
        return a.top();
    }
} H[M];
void die(int x){
    for(auto [i,w]:adj[x])
        H[i].ins(w),rem[i]++;
}
void dfs(int n,int p,int c){
    vis[n]=c;
    vector<int>A,B;
    int ans1=0,ans2=0,h1=rem[n],h2=h1+(p>=0);
    for(auto[a,b]:adj[n]){
        if(a==p)continue;
        if(deg[a]<=c) break;
        dfs(a,n,c),dp[a][0]+=b;
        ans1+=min(dp[a][0],dp[a][1]);
        ans2+=min(dp[a][0],dp[a][1]);
        if(dp[a][1]<dp[a][0]) H[n].ins(dp[a][0]-dp[a][1]),
            B.push_back(dp[a][0]-dp[a][1]), h1++,h2++;
    }
    h1-=c;
    h2-=c;
    while(H[n].sz&&H[n].sz>h2)
        A.push_back(H[n].top()),
        H[n].del(H[n].top());
    dp[n][1]=ans2+H[n].sum;
    while(H[n].sz&&H[n].sz>h1)
        A.push_back(H[n].top()),
        H[n].del(H[n].top());
    dp[n][0]=ans1+H[n].sum;
    for(auto i:A)
        H[n].ins(i);
    for(auto i:B)
        H[n].del(i);
    while(H[n].sz>=adj[n].size()-c)
        H[n].del(H[n].top());
}
std::vector<long long> minimum_closure_costs(I N, std::vector<I> U,std::vector<I> V,std::vector<I> W) {
    int n=N;
    vector<int>Z(n),ans(n);
    for(int i=0;i+1<n;i++){
        int a=U[i]+1,b=V[i]+1,c=W[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        deg[a]++,deg[b]++,ans[0]+=c;
    }
    iota(Z.begin(),Z.end(),1);
    for(int i=1;i<=n;i++)
        sort(adj[i].begin(),adj[i].end(),[](pair<int,int>a,pair<int,int>b){
            return deg[a.first]>deg[b.first];});
    sort(Z.begin(),Z.end(),[](int a,int b){return deg[a]<deg[b];});
    int x=0;
    for(int i=1;i<n;i++){
        while(x<n&&deg[Z[x]]==i)
            die(Z[x++]);
        for(int j=x;j<n;j++) if(vis[Z[j]]-i)
            dfs(Z[j],0,i), ans[i]+=dp[Z[j]][0];
    }
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs(long long int, long long int, long long int)':
roads.cpp:76:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   76 |     while(H[n].sz>=adj[n].size()-c)
      |           ~~~~~~~^~~~~~~~~~~~~~~~~

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