Submission #1108354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108354		SteveBro	Race (IOI11_race)	C++17	100 / 100	235 ms	44388 KiB

race

#include <bits/stdc++.h>

using namespace std;
int mat[200001][2],ll[200001],p;
const int inf=1e9;
struct ura
{
    int t,s;
    bool ok;
}v[200001];
vector < pair<int,int> > g[200001];
int sol;
void dfs(int nod, int n)
{
    bool ok=true;
    v[nod].s=1;
    for(auto x : g[nod])
    {
        if(!v[x.first].ok&&v[nod].t!=x.first)
        {
            v[x.first].t=nod;
            dfs(x.first,n);
            v[nod].s+=v[x.first].s;
            if(v[x.first].s>n/2)
                ok=false;
        }
    }
    if(n-v[nod].s>n/2)
        ok=false;
    if(ok)
        sol=nod;
}
int vc[1000001];
vector <int> r;
int rez=inf;
void dfs1(int nod, int d, int nrm)
{
    if(d<=p)
    {
        rez=min(rez,vc[p-d]+nrm);
        for(auto x : g[nod])
        {
            if(!v[x.first].ok&&x.first!=v[nod].t)
            {
                v[x.first].t=nod;
                dfs1(x.first,d+x.second,nrm+1);
            }
        }
    }
}
void dfs2(int nod, int d, int nrm)
{
    if(d<=p)
    {
        vc[d]=min(nrm,vc[d]);
        r.push_back(d);
        for(auto x : g[nod])
        {
            if(!v[x.first].ok&&x.first!=v[nod].t)
            {
                v[x.first].t=nod;
                dfs2(x.first,d+x.second,nrm+1);
            }
        }
    }
}
void divide(int nod, int nr)
{
    if(nr==1)
        return;
    dfs(nod,nr);
    int ctd=sol;
    for(auto x : g[ctd])
    {
        if(!v[x.first].ok)
        {
            v[x.first].t=ctd;
            dfs1(x.first,x.second,1);
            dfs2(x.first,x.second,1);
        }
    }
    for(int i=0;i<r.size();i++)
        vc[r[i]]=inf;
    r.clear();
    v[ctd].ok=true;
    v[v[ctd].t].s=nr-v[ctd].s;
    for(auto x : g[ctd])
    {
        if(!v[x.first].ok)
        {
            v[x.first].t=ctd;
            divide(x.first,v[x.first].s);
        }
    }
}
int best_path(int n,int k,int h[][2],int l[])
{
    int i;
    for(i=1;i<=k;i++)
        vc[i]=inf;
    for(i=0;i<n-1;i++)
    {
        g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
        g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
    }
    p=k;
    v[1].t=n;
    divide(1,n);
    if(rez==inf)
        rez=-1;
    return rez;
}

Compilation message (stderr)

race.cpp: In function 'void divide(int, int)':
race.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<r.size();i++)
      |                 ~^~~~~~~~~

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