Submission #643072

#	Time	Username	Problem	Language	Result	Execution time	Memory
643072		azberjibiou	Road Closures (APIO21_roads)	C++17	100 / 100	238 ms	63096 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=100010;
int N;
vector <pll> v[mxN], ch[mxN];
vector <ll> seg[mxN], d[mxN];
int sub[mxN];
int u[mxN], dd[mxN];
void dfs0(int now, int pre)
{
    sub[now]=1;
    for(auto [nxt, x] : v[now])   if(nxt!=pre)
    {
        dfs0(nxt, now);
        ch[now].emplace_back(nxt, x);
        sub[now]+=sub[nxt];
    }
    if(ch[now].empty())
    {
        u[now]=dd[now]=now;
        return;
    }
    sort(ch[now].begin(), ch[now].end(), [](pll a, pll b){return sub[a.fi]>sub[b.fi];});
    dd[now]=dd[ch[now][0].fi];
    u[dd[now]]=now;
}
void upd(int typ, int idx, int s1, int e1, int s2, int e2, ll val)
{
    if(s1>e2 || s2>e1)  return;
    if(s2<=s1 && e1<=e2)
    {
        seg[typ][idx]+=val;
        return;
    }
    int mid=(s1+e1)/2;
    upd(typ, 2*idx, s1, mid, s2, e2, val);
    upd(typ, 2*idx+1, mid+1, e1, s2, e2, val);
}
ll solv(int typ, int idx, int s, int e, int pos)
{
    if(s==e)    return seg[typ][idx];
    int mid=(s+e)/2;
    if(pos<=mid)    return seg[typ][idx]+solv(typ, 2*idx, s, mid, pos);
    else    return seg[typ][idx]+solv(typ, 2*idx+1, mid+1, e, pos);
}
void dfs1(int now)
{
    d[now].resize(ch[now].size()+1);
    if(ch[now].empty())
    {
        seg[now].resize(4*sub[u[now]]);
        return;
    }
    for(auto [nxt, x] : ch[now])    dfs1(nxt);
    int fc=ch[now][0].fi;
    u[now]=u[fc];
    upd(fc, 1, 1, sub[u[fc]], sub[fc]+1, sub[now], solv(fc, 1, 1, sub[u[fc]], sub[fc]));
    swap(seg[now], seg[fc]);
    for(auto [nxt, x] : ch[now]) if(nxt!=fc)
    {
        for(int i=1;i<=sub[nxt];i++)
        {
            upd(now, 1, 1, sub[u[now]], i, i, solv(nxt, 1, 1, sub[nxt], i));
        }
        upd(now, 1, 1, sub[u[now]], sub[nxt]+1, sub[now], solv(nxt, 1, 1, sub[nxt], sub[nxt]));
    }
    multiset <ll> lo, hi;
    vector <pll> ct;
    ct=ch[now];
    sort(ct.begin(), ct.end(), [](pll a, pll b){return ch[a.fi].size()>ch[b.fi].size();});
    ll tsum=0;
    for(auto [nxt, x] : ct) tsum+=x;
    fc=ct[0].fi;
    int lim=max(ch[fc].size(), ch[now].size());
    upd(now, 1, 1, sub[u[now]], lim+1, sub[now], tsum);
    /*for(int i=1;i<=sub[u[now]];i++)
    {
        printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
    }*/
    ll del=0;
    while(ct.size() && ch[ct.back().fi].empty())
    {
        hi.insert(ct.back().se);
        del+=ct.back().se;
        ct.pop_back();
    }
    for(int i=1;i<=lim;i++)
    {
        while(hi.size()<i && lo.size())
        {
            hi.insert(*lo.rbegin());
            del+=*lo.rbegin();
            auto it=lo.end();   it--;
            lo.erase(it);
        }
        while(hi.size()>i)
        {
            lo.insert(*hi.begin());
            del-=*hi.begin();
            hi.erase(hi.begin());
        }
        for(auto [nxt, x] : ct)
        {
            if(-d[nxt][i]+x>0)
            {
                hi.insert(-d[nxt][i]+x);
                del+=(-d[nxt][i]+x);
            }
        }
        vector <ll> tsh;
        while(hi.size()>i)
        {
            tsh.push_back(*hi.begin());
            del-=*hi.begin();
            hi.erase(hi.begin());
        }
        /*printf("hi: ");
        for(auto ele : hi)  printf("%lld ", ele);
        printf("\nlo: ");
        for(auto ele : lo)  printf("%lld ", ele);
        printf("\n");*/
        if(hi.size()==i && i<=ch[now].size())    d[now][i]=*hi.begin();
        upd(now, 1, 1, sub[u[now]], i, i, del);
        for(ll ele : tsh)
        {
            hi.insert(ele);
            del+=ele;
        }
        for(auto [nxt, x] : ct)
        {
            if(-d[nxt][i]+x>0)
            {
                hi.erase(hi.find(-d[nxt][i]+x));
                del-=(-d[nxt][i]+x);
            }
        }
        while(ct.size() && ch[ct.back().fi].size()==i)
        {
            lo.insert(ct.back().se);
            ct.pop_back();
        }
        while(lo.size() && hi.size() && *lo.rbegin()>*hi.begin())
        {
            hi.insert(*lo.rbegin());
            del+=*lo.rbegin();
            auto it=lo.end();   it--;
            lo.erase(it);
        }
    }
    /*for(int i=1;i<=sub[u[now]];i++)
    {
        printf("dp[%d][%d]=%lld\n", now, i, solv(now, 1, 1, N, i));
    }*/
    //printf("end %d\n", now);
}
vector<long long> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
    N=n;
    for(int i=0;i<N-1;i++)
    {
        U[i]++;
        V[i]++;
        v[U[i]].emplace_back(V[i], W[i]);
        v[V[i]].emplace_back(U[i], W[i]);
    }
    dfs0(1, -1);
    //for(int i=1;i<=N;i++)   printf("u[%d]=%d\n", i, u[i]);
    dfs1(1);
    //for(int i=1;i<=N;i++)   for(int j=1;j<d[i].size();j++)  printf("d[%d][%d]=%lld\n", i, j, d[i][j]);
    vector <ll> ans;
    ans.resize(N);
    ll sum=0;
    for(int ele : W)    sum+=ele;
    ans[0]=sum;
    for(int i=1;i<N;i++)    ans[i]=sum-solv(1, 1, 1, N, i);
    return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void dfs1(int)':
roads.cpp:94:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         while(hi.size()<i && lo.size())
      |               ~~~~~~~~~^~
roads.cpp:101:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         while(hi.size()>i)
      |               ~~~~~~~~~^~
roads.cpp:116:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |         while(hi.size()>i)
      |               ~~~~~~~~~^~
roads.cpp:127:21: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |         if(hi.size()==i && i<=ch[now].size())    d[now][i]=*hi.begin();
      |            ~~~~~~~~~^~~
roads.cpp:127:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         if(hi.size()==i && i<=ch[now].size())    d[now][i]=*hi.begin();
      |                            ~^~~~~~~~~~~~~~~~
roads.cpp:142:51: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  142 |         while(ct.size() && ch[ct.back().fi].size()==i)
      |                            ~~~~~~~~~~~~~~~~~~~~~~~^~~

• 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