Submission #218025

#	Time	Username	Problem	Language	Result	Execution time	Memory
218025		Andrei_Cotor	Race (IOI11_race)	C++11	43 / 100	334 ms	71032 KiB

race

#include<race.h>
#include<vector>
#include<set>

using namespace std;

int nrPaths;
set<pair<long long,int> > S[200005];
vector<pair<int,int> > A[200005];
int HPath[200005],Lev[200005];
long long Dist[200005];

int dfs(int nod, int p, int L)
{
    int rez=1000000000;
    for(auto other:A[nod])
    {
        if(other.first==p)
            continue;

        Dist[other.first]=Dist[nod]+other.second;
        Lev[other.first]=Lev[nod]+1;
        rez=min(rez,dfs(other.first,nod,L));

        if(S[HPath[other.first]].size()>S[HPath[nod]].size())
            HPath[nod]=HPath[other.first];
    }

    if(HPath[nod]==0)
        HPath[nod]=++nrPaths;

    int path=HPath[nod];
    for(auto other:A[nod])
    {
        if(other.first==p || path==HPath[other.first])
            continue;

        for(auto el:S[HPath[other.first]])
        {
            int dist=L-(el.first-Dist[nod])+Dist[nod];
            if(dist>Dist[nod])
            {
                set<pair<long long,int> >::iterator it=S[path].lower_bound({dist,0});
                if(it!=S[path].end() && (*it).first==dist)
                    rez=min(rez,(*it).second+el.second-2*Lev[nod]);
            }

            set<pair<long long,int> >::iterator it=S[path].lower_bound({el.first,0});
            if(it!=S[path].end() && (*it).first==el.first)
            {
                if(el.second<(*it).second)
                {
                    S[path].erase(it);
                    S[path].insert(el);
                }
            }
            else
                S[path].insert(el);
        }
    }

    S[path].insert({Dist[nod],Lev[nod]});
    set<pair<long long,int> >::iterator it=S[path].lower_bound({Dist[nod]+L,0});
    if(it!=S[path].end() && (*it).first==Dist[nod]+L)
        rez=min(rez,(*it).second-Lev[nod]);

    return rez;
}

int best_path(int n, int k, int E[][2], int L[])
{
    for(int i=0; i<=n-2; i++)
    {
        A[E[i][0]].push_back({E[i][1],L[i]});
        A[E[i][1]].push_back({E[i][0],L[i]});
    }

    int rez=dfs(0,-1,k);
    if(rez==1000000000)
        rez=-1;

    return rez;
}

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