Submission #1082156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082156		alexander707070	Road Closures (APIO21_roads)	C++14	78 / 100	2055 ms	193112 KiB

roads

#include<bits/stdc++.h>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include "roads.h"
 
#define MAXN 100007
using namespace std;
 
const long long inf=1e9;
 
int n,a,b,k,sz[MAXN];
long long sum;
 
vector<int> toadd[MAXN];
vector< pair<int,int> > v[MAXN],g[MAXN];
 
long long dp[MAXN][2];
int li[MAXN][2],tim;
 
struct node{
    int l,r,cnt;
    long long sum;
};

int num;
node tree[100*MAXN];
 
struct dynamicST{
    int root;

    void init(){
        num++; root=num;
    }
 
    void add_node(){
        num++;
    }
 
    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v].cnt+=val;
            tree[v].sum+=val*l;
        }else{
            int mid=(l+r)/2;
 
            if(pos<=mid){
                if(tree[v].l==0){
                    add_node(); tree[v].l=num;
                }
                
                update(tree[v].l,l,mid,pos,val);
            }else{
                if(tree[v].r==0){
                    add_node(); tree[v].r=num;
                }
                
                update(tree[v].r,mid+1,r,pos,val);
            }
 
            tree[v].cnt=tree[tree[v].l].cnt+tree[tree[v].r].cnt;
            tree[v].sum=tree[tree[v].l].sum+tree[tree[v].r].sum;
        }
    }
 
    int getcnt(int v,int l,int r,int ll,int rr){
        if(v==0)return 0;
        if(tree[v].cnt==0)return 0;
 
        if(l==ll and r==rr){
            return tree[v].cnt;
        }else{
            int mid=(l+r)/2;
            return getcnt(tree[v].l,l,mid,ll,min(mid,rr)) + getcnt(tree[v].r,mid+1,r,max(mid+1,ll),rr);
        }
    }
 
    int getkth(int v,int l,int r,int pos){
        if(l==r)return l;
 
        int mid=(l+r)/2;
        if(tree[tree[v].l].cnt>=pos)return getkth(tree[v].l,l,mid,pos);
        else return getkth(tree[v].r,mid+1,r,pos-tree[tree[v].l].cnt);
    }

    long long getsum(int v,int l,int r,int ll,int rr){
        if(v==0)return 0;
 
        if(l==ll and r==rr){
            return tree[v].sum;
        }else{
            int mid=(l+r)/2;
            return getsum(tree[v].l,l,mid,ll,min(mid,rr)) + getsum(tree[v].r,mid+1,r,max(ll,mid+1),rr);
        }
    }
};
 
struct edges{
    dynamicST tree;
    multiset<int> z;
 
    void add(int x){
        tree.update(tree.root,1,inf,x,1);
        z.insert(x);
    }
 
    void rem(int x){
        tree.update(tree.root,1,inf,x,-1);
        z.erase(z.find(x));
    }
 
    int query(long long x){

        if(z.size()<=20){
            int res=0;
            for(int k:z){
                if(k<=x)res++;
            }
            return res;
        }

        if(x>inf)x=inf;
        return tree.getcnt(tree.root,1,inf,1,x);
    }
 
    int getkth(int x){
        return tree.getkth(tree.root,1,inf,x);
    }
 
    long long getsum(int x){
        int val=getkth(x);
        long long total=query(val);
 
        return tree.getsum(tree.root,1,inf,1,val)- (total-x)*val;
    }
 
}bonus[MAXN];
 
long long ff(int x,int p,bool par){
 
    if(li[x][par]==tim)return dp[x][par];
    li[x][par]=tim;
    dp[x][par]=0;
 
    vector<long long> s;
    for(int i=0;i<v[x].size();i++){
 
        if(v[x][i].first==p){
            if(par)dp[x][par]+=v[x][i].second;
            continue;
        }
 
        s.push_back(ff(v[x][i].first,x,true)-ff(v[x][i].first,x,false));
        dp[x][par]+=ff(v[x][i].first,x,false);
    }
 
    sort(s.begin(),s.end());
 
    int pt=0,pos=-1,cnt=0;
    while(pt<s.size() and s[pt]<0){
        dp[x][par]+=s[pt]; pt++;
    }
 
    if(sz[x]-k-par-pt<=0)return dp[x][par];
    
    int l=pt-1,r=s.size(),tt;
    while(l+1<r){
        tt=(l+r)/2;
        cnt=bonus[x].query(s[tt]);

        if(sz[x]-k-par-(tt+1)-cnt<=0){
            r=tt;
        }else{
            l=tt;
        }
    }

    if(r<s.size()){
        pos=r;
        cnt=bonus[x].query(s[r]);
    }

    if(pos==-1){
        for(int i=pt;i<s.size();i++)dp[x][par]+=s[i];
        dp[x][par]+=bonus[x].getsum(sz[x]-k-par-int(s.size()));
        return dp[x][par];
    }
 
    if(sz[x]-k-par-(pos+1)-cnt==0){
        for(int i=pt;i<=pos;i++)dp[x][par]+=s[i];
        dp[x][par]+=bonus[x].getsum(sz[x]-k-par-(pos+1));
    }else{
        for(int i=pt;i<=pos-1;i++)dp[x][par]+=s[i];
        dp[x][par]+=bonus[x].getsum(sz[x]-k-par-pos);
    }
 
    return dp[x][par];
}
 
bool in[MAXN];
vector<int> roots;
 
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
    n=N;

    for(int i=1;i<=n;i++)bonus[i].tree.init();
 
    for(int i=1;i<=n-1;i++){
        a=U[i-1]; b=V[i-1];
        a++; b++;
 
        g[a].push_back({b,W[i-1]});
        g[b].push_back({a,W[i-1]});
 
        sz[a]++; sz[b]++;
 
        sum+=W[i-1];
    }

    vector<long long> res;

    for(int i=1;i<=n;i++){
        for(int f=0;f<g[i].size();f++){
            bonus[i].add(g[i][f].second);
        }
    }

    if(g[a].size()==n-1){
        sort(W.begin(),W.end());
        long long z=0;

        for(int i=0;i<=n-1;i++){
            res.push_back(z);
            if(i<n-1)z+=W[i];
        }
        reverse(res.begin(),res.end());

        return res;
    }
 
    for(int i=1;i<=n;i++){
        toadd[sz[i]-1].push_back(i);
    }
 
    for(int i=n-1;i>=1;i--){
 
        for(int f:toadd[i]){      
            for(pair<int,int> k:g[f]){
                if(!in[k.first])continue;
 
                v[f].push_back({k.first,k.second});
                v[k.first].push_back({f,k.second});
 
                bonus[f].rem(k.second);
                bonus[k.first].rem(k.second);
            }
 
            in[f]=true;
            roots.push_back(f);
        }
 
        long long curr=0;
        tim++; k=i;
 
        for(int f:roots){
            if(li[f][0]==tim)continue;
            curr+=ff(f,0,0);
        }
 
        res.push_back(curr);
    }
    
 
    res.push_back(sum);
    reverse(res.begin(),res.end());
 
    return res;
}
 
/*int main(){
 
    vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
    vector<long long> s=minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
 
    for(long long i:s)cout<<i<<" ";
 
    return 0;
}*/

Compilation message (stderr)

roads.cpp: In function 'long long int ff(int, int, bool)':
roads.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
roads.cpp:161:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     while(pt<s.size() and s[pt]<0){
      |           ~~^~~~~~~~~
roads.cpp:179:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     if(r<s.size()){
      |        ~^~~~~~~~~
roads.cpp:185:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |         for(int i=pt;i<s.size();i++)dp[x][par]+=s[i];
      |                      ~^~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:224:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |         for(int f=0;f<g[i].size();f++){
      |                     ~^~~~~~~~~~~~
roads.cpp:229:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  229 |     if(g[a].size()==n-1){
      |        ~~~~~~~~~~~^~~~~

• 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: 0 / 22