Submission #403507

#	Time	Username	Problem	Language	Result	Execution time	Memory
403507		Newtech66	Race (IOI11_race)	C++17	43 / 100	960 ms	262148 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
typedef long long int lol;
vector<vector<pair<int,int> > > g(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> del;
int ans=INT_MAX;

void dfssz(int u,int p=-1)
{
    subsz[u]=1;
    for(auto ch:g[u])
    {
        if(ch.first==p) continue;
        if(!del.test(ch.first))
        {
            dfssz(ch.first,u);
            subsz[u]+=subsz[ch.first];
        }
    }
}

int getcen(int u,int sz,int p=-1)
{
    for(auto ch:g[u])
    {
        if(ch.first==p) continue;
        if(!del.test(ch.first))
        {
            if(subsz[ch.first]>sz/2)    return getcen(ch.first,sz,u);
        }
    }
    return u;
}

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(u==m[len][0].second)
        {
            if(nm<=m[len][0].first)
            {
                m[len].pop_front();
                m[len].emplace_front(nm,u);
            }
        }else
        {
            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)
        {
            if(u==m[len][0].second)
            {
                m[len].pop_front();
            }else
            {
                m[len].pop_back();
            }
            m[len].emplace_front(nm,u);
        }else if(nm<=m[len][1].first)
        {
            if(u!=m[len][0].second)
            {
                m[len].pop_back();
                m[len].emplace_back(nm,u);
            }
        }
    }
}

void solve(int u,map<int,deque<pair<int,int> > > &m,int len,int K,int dep,int z,int p)
{
    for(auto ch:g[u])
    {
        if(ch.first==p) continue;
        if(!del.test(ch.first))
        {
            if(len+ch.second<=K)
            {
                place(m,len+ch.second,1+dep,z);
                solve(ch.first,m,len+ch.second,K,1+dep,z,u);
            }
        }
    }
}

void centroid(int u,const int& K)
{
    //find subtree sizes
    dfssz(u);
    //get centroid
    int C=getcen(u,subsz[u]);
    //cout<<"C: "<<C<<endl;
    //solve
    map<int,deque<pair<int,int> > > m;
    for(auto ch:g[C])
    {
        if(!del.test(ch.first))
        {
            if(ch.second<=K)
            {
                place(m,ch.second,1,ch.first);
                solve(ch.first,m,ch.second,K,1,ch.first,C);
            }
        }
    }
    /*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].begin()->first);
    }
    for(auto p:m)
    {
        if(m.find(K-p.first)!=m.end())
        {
            if(m[K-p.first].begin()->second==p.second.begin()->second)
            {
                if(m[K-p.first].size()>=2)
                {
                    auto it=++(m[K-p.first].begin());
                    ans=min(ans,p.second.begin()->first+it->first);
                }
            }else
            {
                ans=min(ans,p.second.begin()->first+m[K-p.first].begin()->first);
            }
        }
    }
    //end
    del.flip(C);
    for(auto ch:g[C])
    {
        if(!del.test(ch.first)) centroid(ch.first,K);
    }
}
 
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].emplace_back(v,L[i]);
        g[v].emplace_back(u,L[i]);
    }
    centroid(0,K);
    if(ans==INT_MAX)  return -1;
    else  return ans;
}

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