Submission #402887

#	Time	Username	Problem	Language	Result	Execution time	Memory
402887		Newtech66	Race (IOI11_race)	C++17	0 / 100	5 ms	6884 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
vector<vector<pair<int,int> > > g(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> del;
int ans=INT_MAX;
 
void findsubsz(int u,int p=-1)
{
    subsz[u]=1;
    for(auto ch:g[u])
    {
        if(ch.first!=p)
        {
            findsubsz(ch.first,u);
            subsz[u]+=subsz[ch.first];
        }
    }
}
 
void place(map<int,deque<pair<int,int> > > &m,int len,int nm,int u)
{
    if(m.find(len)==m.end())
    {
        m[len].emplace_back(nm,u);
    }else if(m[len].size()==1)
    {
        if(nm<=m[len][0].first)
        {
            m[len].emplace_front(nm,u);
        }else
        {
            m[len].emplace_back(nm,u);
        }
    }else
    {
        if(nm<=m[len][0].first)
        {
            m[len].pop_back();
            m[len].emplace_front(nm,u);
        }else if(nm<=m[len][1].first)
        {
            m[len].pop_back();
            m[len].emplace_back(nm,u);
        }
    }
}
 
void solve(int u,map<int,deque<pair<int,int> > > &m,int len,int dep,int K,int z=-1,int p=-1)
{
    for(auto ch:g[u])
    {
        if(ch.first!=p && !del.test(ch.first))
        {
            if(len+ch.second<=K)
            {
                if(p==-1)   z=ch.first;
                place(m,len+ch.second,dep+1,z);
                solve(ch.first,m,len+ch.second,dep+1,K,z,u);
            }
        }
    }
}
 
void cendcmp(int u,int sz,int K,int p=-1)
{
    //cout<<u<<endl;
    int mx=sz-subsz[u],pos=p;
    for(auto ch:g[u])
    {
        if(!del.test(ch.first) && ch.first!=p)
        {
            if(mx<subsz[ch.first])
            {
                pos=ch.first;
                mx=subsz[ch.first];
            }
        }
    }
    if(mx<=sz/2)
    {
        //cout<<"Centroid found "<<u<<endl;
        map<int,deque<pair<int,int> > > m;
        solve(u,m,0,0,K);
        /*for(auto p:m)
        {
            cout<<p.first<<": ";
            for(auto e:p.second)
            {
                cout<<"("<<e.first<<","<<e.second<<") ";
            }
            cout<<endl;
        }*/
        if(m.find(K)!=m.end())  ans=min(ans,m[K][0].first);
        for(auto p:m)
        {
            int len=p.first,nm=p.second[0].first,ch=p.second[0].second;
            if(m.find(K-len)!=m.end())
            {
                if(m[K-len][0].second!=ch)
                {
                    ans=min(ans,nm+m[K-len][0].first);
                }else
                {
                    if(m[K-len].size()==2)
                    {
                        ans=min(ans,nm+m[K-len][1].first);
                    }
                }
            }
        }
        del.flip(u);
        for(auto ch:g[u])
        {
            if(!del.test(ch.first))
            {
                cendcmp(ch.first,subsz[ch.first],K,-1);
            }
        }
    }else
    {
        if(pos!=-1)   cendcmp(pos,sz,K,u);
    }
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    for(int i=0;i<N-1;i++)
    {
        int u=H[i][0],v=H[i][1];
        g[u].push_back({v,L[i]});
        g[v].push_back({u,L[i]});
    }
    findsubsz(0);
    cendcmp(0,N,K);
    if(ans==INT_MAX)  return -1;
    else  return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57