Submission #559663

#	Time	Username	Problem	Language	Result	Execution time	Memory
559663		fcmalkcin	Road Closures (APIO21_roads)	C++17	100 / 100	483 ms	89604 KiB

roads

#include <bits/stdc++.h>
using namespace std;

#define ll  long long 
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+50;
const ll mod=1e9+7  ;
const ll base=1e18;

#include "roads.h"

/// i believe myself
/// goal 0/7

set<pll> adj[maxn];
pll anc[maxn];
struct tk
{
    vector<pll> st;
    vector<ll> vt;
    ll n;
    void setup()
    {
        n=vt.size();
        st=vector<pll> (4*n+5, {0,0});
    }
    pll mer(pll a,pll b)
    {
        return make_pair(a.ff+b.ff,a.ss+b.ss);
    }
    void update(ll id,ll left,ll right,ll x)
    {
        if (x>right||x<left)
            return ;
        if (left==right)
        {
            st[id].ff+=1;
            st[id].ss+=vt[left-1];
            return ;
        }
        ll mid=(left+right)/2;
        update(id*2,left,mid,x);
        update(id*2+1,mid+1,right,x);
        st[id]=mer(st[id*2],st[id*2+1]);
    }
    void update1(ll pos)
    {
        pos=lower_bound(vt.begin(),vt.end(),pos)-vt.begin()+1;
        update(1,1,n,pos);
    }
    pll get(ll id,ll left,ll right,ll x,ll y)
    {
        if (x>right||y<left)
            return make_pair(0,0);
        if (x<=left&&y>=right)
            return st[id];
        ll mid=(left+right)/2;
        return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
    }
    ll get1(ll id,ll left,ll right,ll p)
    {
        if (left==right)
            return left;
        ll mid=(left+right)/2;
        if (st[id*2].ff>=p)
            return get1(id*2,left,mid,p);
        return get1(id*2+1,mid+1,right,p-st[id*2].ff);
    }
    ll get2(ll p)
    {
        if (p==0)
            return 0;
        ll pos=get1(1,1,n,p);
        auto h=get(1,1,n,1,pos);
        return h.ss-(h.ff-p)*vt[pos-1];
    }
};
tk gr[maxn];
ll cnt=0;
ll f[maxn];
bool dd[maxn];
ll sl[maxn];

void dfs(ll u,ll par)
{
    cnt++;
    f[u]=cnt;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        gr[u].vt.pb(p.ss);
        if (to==par)
            continue;
        anc[to]=make_pair(u,p.ss);
        dfs(to,u);

    }
    sort(gr[u].vt.begin(),gr[u].vt.end());
    gr[u].vt.resize(unique(gr[u].vt.begin(),gr[u].vt.end())-gr[u].vt.begin());
    gr[u].setup();
}
set<pll> st;
void ers(ll u)
{
    st.erase(make_pair(f[u],u));
    for (auto to:adj[u])
    {
        ll h=to.ff;
        ll w=to.ss;
        adj[h].erase(make_pair(u,w));
        gr[h].update1(w);
        sl[h]++;
    }
  /*  gr[anc[u].ff].update1(anc[u].ss);
    sl[anc[u].ff]++;*/
}
ll dp[maxn][2];
ll k;
void dfs1(ll u,ll par,ll w)
{
    dp[u][0]=base;
    dp[u][1]=base;
    dd[u]=1;
    vector<ll> vt;
    ll cntnw=0;
    for (auto p:adj[u])
    {
        ll to=p.ff;
        ll w=p.ss;
        if (to==par)
            continue;
        dfs1(to,u,w);
        cntnw+=dp[to][0];
        if (dp[to][0]>dp[to][1])
        {
            vt.pb(dp[to][1]-dp[to][0]);
        }
    }
    sort(vt.begin(),vt.end());
    ll pre=cntnw;
    for (int i=-1; i<min(k,(ll)vt.size()); i++)
    {
        if (i!=-1)
        {
            cntnw+=vt[i];
        }
        ll slnw=i+1+sl[u];
        ll h=max((ll)0,slnw-k);
        dp[u][0]=min(dp[u][0],cntnw+gr[u].get2(h)+w);
        if (k==2)
        {
        //    cout <<cntnw+gr[u].get2(h)+w<<" "<<u<<" "<<h<<" "<<slnw<<" wtf"<<endl;
        }
    }
    cntnw=pre;
    for (int i=-1; i<min(k,(ll)vt.size()); i++)
    {
        if (i!=-1)
        {
            cntnw+=vt[i];
        }
        ll slnw=i+2+sl[u];
        ll h=max((ll)0,slnw-k);
        if (h<=sl[u])
            dp[u][1]=min(dp[u][1],cntnw+gr[u].get2(h));
    }
}
vector<ll> minimum_closure_costs(int N, vector<int> U,vector<int> V,vector<int> W)
{
    ll n=N;
    vector<pll> vt;
    for (int i=0; i<U.size(); i++)
    {
        adj[U[i]+1].insert(make_pair(V[i]+1,W[i]));
        adj[V[i]+1].insert(make_pair(U[i]+1,W[i]));
    }
    for (int i=1; i<=n; i++)
    {
        vt.pb(make_pair(adj[i].size(),i));
    }
    sort(vt.begin(),vt.end());
    dfs(1,0);
    for (int i=1; i<=n; i++)
        st.insert(make_pair(f[i],i));
    ll id=0;
    vector<ll> res;
    for (int t=0; t<=n-1; t++)
    {
        k=t;
        while (id<vt.size()&&vt[id].ff<=t)
        {
            ll pos=vt[id].ss;
            ers(pos);
        //    cout <<pos<<" "<<t<<" chk1"<<endl;
            id++;
        }
       /* if (t==2)
        {
            for(auto p:st)
            {
                cout <<p.ff<<" "<<p.ss<<" chk2"<<endl;
            }
            for (auto p:adj[3])
            {
                cout <<p.ff<<" "<<p.ss<<" chk3"<<endl;
            }
        }*/
        ll ans=0;
        for (auto to:st)
        {
            if (dd[to.ss])
                continue;
            dfs1(to.ss,0,0);
            ans+=dp[to.ss][0];
        }
        res.pb(ans);
        for (auto to:st)
        {
            dd[to.ss]=0;
        }
    }
    return res;
}



/*5
0 1 1
0 2 4
0 3 3
2 4 2
*/

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:178:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for (int i=0; i<U.size(); i++)
      |                   ~^~~~~~~~~
roads.cpp:196:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         while (id<vt.size()&&vt[id].ff<=t)
      |                ~~^~~~~~~~~~

• 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