Submission #1081953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081953		alexander707070	Road Closures (APIO21_roads)	C++14	24 / 100	2107 ms	1048576 KiB

roads

#include<bits/stdc++.h>
#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 edges{
    unordered_map<int,int> fenwick;
    unordered_map<int,long long> sum;

    void add(int x){
        int val=x;

        while(x<=inf){
            fenwick[x]++;
            sum[x]+=val;

            x+=(x & (-x));
        }
    }

    void rem(int x){
        int val=x;

        while(x<=inf){
            fenwick[x]--;
            sum[x]-=val;

            x+=(x & (-x));
        }
    }

    int query(int x){
        int res=0;
        while(x>=1){
            res+=fenwick[x];
            x-=(x & (-x));
        }
        return res;
    }

    int getkth(int x){
        int l=-1,r=inf,mid;

        while(l+1<r){
            mid=(l+r)/2;
            if(query(mid)>=x){
                r=mid;
            }else{
                l=mid;
            }
        }

        return r;
    }

    long long getsum(int x){
        
        int r=getkth(x);
        long long s=query(r),res=0,e=x;
        x=r;

        while(x>=1){
            res+=sum[x];
            x-=(x & (-x));
        }

        return res-(s-e)*r;
    }

}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];

    for(int i=pt;i<s.size();i++){
        cnt=bonus[x].query(s[i]);
        if(sz[x]-k-par-(i+1)-cnt<=0){
            pos=i; break;
        }
    }

    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-1;i++){
        a=U[i-1]; b=V[i-1];
        a++; b++;

        bonus[a].add(W[i-1]);
        bonus[b].add(W[i-1]);

        g[a].push_back({b,W[i-1]});
        g[b].push_back({a,W[i-1]});

        sz[a]++; sz[b]++;

        sum+=W[i-1];
    }

    for(int i=1;i<=n;i++){
        toadd[sz[i]-1].push_back(i);
    }

    vector<long long> res;

    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:91: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]
   91 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
roads.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     while(pt<s.size() and s[pt]<0){
      |           ~~^~~~~~~~~
roads.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=pt;i<s.size();i++){
      |                  ~^~~~~~~~~
roads.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=pt;i<s.size();i++)dp[x][par]+=s[i];
      |                      ~^~~~~~~~~

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