Submission #402787

#	Time	Username	Problem	Language	Result	Execution time	Memory
402787		Newtech66	Race (IOI11_race)	C++17	0 / 100	8 ms	10188 KiB

race

//#include "race.h"
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
vector<vector<pair<int,int> > > g(MAXN);
vector<vector<pair<int,int> > > ceng(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> vis;
vector<map<int,int> > sol(MAXN);
int cenroot=-1;
int ans=INT_MAX;

void solve(int u,const int& K)
{
    vis.flip(u);
    map<int,deque<pair<int,int> > > m;
    for(auto ch:g[u])
    {
        if(!vis.test(ch.first))
        {
            solve(ch.first,K);
            for(auto p:sol[ch.first])
            {
                int len=p.first+ch.second,nm=p.second+1;
                if(len<=K)
                {
                    if(sol[u].find(len)==sol[u].end())
                    {
                        sol[u][len]=INT_MAX;
                    }
                    sol[u][len]=min(sol[u][len],nm);
                    if(m.find(len)==m.end())
                    {
                        m[len].emplace_back(nm,ch.first);
                    }else if(m[len].size()==1)
                    {
                        if(nm<=m[len][0].first)
                        {
                            m[len].emplace_front(nm,ch.first);
                        }else
                        {
                            m[len].emplace_back(nm,ch.first);
                        }
                    }else
                    {
                        if(nm<=m[len][0].first)
                        {
                            m[len].pop_back();
                            m[len].emplace_front(nm,ch.first);
                        }else if(nm<=m[len][1].first)
                        {
                            m[len].pop_back();
                            m[len].emplace_back(nm,ch.first);
                        }
                    }
                }
            }
        }
    }
    if(sol[u].find(K)!=sol[u].end())    ans=min(ans,sol[u][K]);
    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);
                }
            }
        }
    }
    sol[u][0]=0;
}
                                               

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(1);
  vis.clear();
  makeceng(1);
  vis.clear();
  solve(cenroot);*/
  solve(0,K);
  return ans;
}

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