Submission #1288452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288452		vivkostov	Race (IOI11_race)	C++20	0 / 100	5 ms	9784 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct cell
{
    long long int to,st;
};
struct ver
{
    long long int lon,br;
};
long long int n,k,otg,dist=1e9,lead[200005],con[200005],dis[200005];
vector<cell>v[200005];
map<long long int,ver>m[200005];
void dfs(int beg,int par)
{
    int w;
    long long int ma=0,ind=0,va,cdi;
    ver h;
    if(beg!=0&&v[beg].size()==1)
    {
        lead[beg]=beg;
        dis[beg]=0;
        h.br=1;
        h.lon=0;
        m[beg][0]=h;
        return;
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].to;
        if(w==par)continue;
        dfs(w,beg);
        con[lead[w]]+=v[beg][i].st;
        dis[lead[w]]++;
        if(ma<m[lead[w]].size())
        {
            ma=m[lead[w]].size();
            ind=w;
        }
    }
    lead[beg]=lead[ind];
    h.br=1;
    h.lon=-dis[lead[beg]];
    m[lead[beg]][-con[lead[beg]]]=h;
    //cout<<ind<<" "<<ma<<endl;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].to;
        if(w==par||w==ind)continue;
        for(auto j=m[lead[w]].begin();j!=m[lead[w]].end();j++)
        {
            va=j->first;
            va=k-va-con[lead[w]]-con[lead[beg]];
            cdi=m[lead[beg]][va].lon+j->second.lon+dis[lead[beg]]+dis[lead[w]];
            //cout<<va<<" "<<cdi<<" "<<con[lead[w]]<<" "<<con[lead[beg]]<<endl;
            if(m[lead[beg]][va].br>0&&cdi<=dist)
            {
                //cout<<beg<<"1111"<<endl;
                if(cdi<dist)
                {
                    dist=cdi;
                    otg=0;
                }
                otg+=m[lead[beg]][va].br;
            }
            if(m[lead[beg]][va].br==0)
            {
                m[lead[beg]].erase(va);
            }
            va=j->first;
            va=va+con[lead[w]]-con[lead[beg]];
            j->second.lon+=dis[lead[w]]-dis[lead[beg]];
            if(m[lead[beg]][va].lon>j->second.lon)
            {
                m[lead[beg]][va]=j->second;
            }
            else if(m[lead[beg]][va].lon==j->second.lon)
            {
                m[lead[beg]][va].br+=j->second.br;
            }
        }
    }
    va=k-con[lead[beg]];
    cdi=m[lead[beg]][va].lon+dis[lead[beg]];
    if(m[lead[beg]][va].br>0&&cdi<=dist)
    {
        if(cdi<dist)
        {
            dist=cdi;
            otg=0;
        }
        otg+=m[lead[beg]][va].br;
    }
    if(m[lead[beg]][va].br==0)
    {
        m[lead[beg]].erase(va);
    }
    //cout<<endl;
    //cout<<beg<<endl;
    //cout<<m[lead[beg]].size()<<endl;
    //cout<<beg<<" "<<con[lead[beg]]<<" "<<dis[lead[beg]]<<endl;
    for(auto i=m[lead[beg]].begin();i!=m[lead[beg]].end();i++)
    {
        //cout<<i->first<<" "<<i->second.lon<<" "<<i->second.br<<endl;
    }
    //cout<<endl;
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    cell c;
    for(int i=0;i<n-1;i++)
    {
        c.st=L[i];
        c.to=H[i][1];
        v[H[i][0]].push_back(c);
        c.to=H[i][0];
        v[H[i][1]].push_back(c);
    }
    dfs(0,0);
    //cout<<otg<<" "<<dist<<endl;
    if(otg==0)
    {
        //cout<<-1<<endl;
        return -1;
    }
    return otg*2;
}

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