Submission #59513

#	Time	Username	Problem	Language	Result	Execution time	Memory
59513		Vahan	Race (IOI11_race)	C++17	100 / 100	1384 ms	81648 KiB

race

#include "race.h"
#include<vector>
#include<iostream>
using namespace std;
#define mp make_pair
vector< pair<int,int> > g[300000];
int n,rr,s[300000],k,tm[1000008],us[300000];
const int MAXH=1000000;
void dfs(int v,int p)
{
    n++;
    s[v]=0;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        if(to==p || us[to])
            continue;
        dfs(to,v);
    }
}
int centr(int v,int p)
{
    s[v]=1;
    int e=-1;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        if(to==p || us[to])
            continue;
        centr(to,v);
        s[v]+=s[to];
        e=max(e,s[to]);
    }
    e=max(e,n-s[v]);
    if(e<=n/2)
        rr=v;
}
void dfsh(int v,int p,int h,int qan)
{
    if(h<=k)
    {
        if(tm[k-h]>=0)
        {
            if(tm[k]==-1)
                tm[k]=tm[k-h]+qan;
            tm[k]=min(tm[k],tm[k-h]+qan);
        }
    }
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        int dis=g[v][i].second;
        if(to==p || us[to])
            continue;
        dfsh(to,v,dis+h,qan+1);
    }
}
void dfsm(int v,int p,int h,int qan)
{
    if(h<MAXH)
    {
        if(tm[h]==-1)
            tm[h]=qan;
        tm[h]=min(tm[h],qan);
    }
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        int dis=g[v][i].second;
        if(to==p || us[to])
            continue;
        dfsm(to,v,dis+h,qan+1);
    }
}
void dfsg(int v,int p,int h)
{
    if(h<=MAXH && h!=k)
        tm[h]=-1;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i].first;
        int dis=g[v][i].second;
        if(to==p || us[to])
            continue;
        dfsg(to,v,dis+h);
    }
}
void ans(int v,int p)
{
    rr=0;
    n=0;
    dfs(v,p);
    centr(v,p);
    int r=rr;
    us[r]=1;
    for(int i=0;i<g[r].size();i++)
    {
        int to=g[r][i].first;
        int dis=g[r][i].second;
        if(to==p || us[to])
            continue;
        dfsh(to,r,dis,1);
        dfsm(to,r,dis,1);
    }
    for(int i=0;i<g[r].size();i++)
    {
        int to=g[r][i].first;
        int dis=g[r][i].second;
        if(to==p || us[to])
            continue;
        dfsg(to,r,dis);
    }
    for(int i=0;i<g[r].size();i++)
    {
        int to=g[r][i].first;
        int dis=g[r][i].second;
        if(to==p || us[to])
            continue;
        ans(to,r);
    }
    for(int i=0;i<g[r].size();i++)
    {
        int to=g[r][i].first;
        int dis=g[r][i].second;
        if(to==p || us[to])
            continue;
        dfsh(to,r,dis,1);
        dfsm(to,r,dis,1);
        ans(to,r);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    tm[0]=0;
    for(int i=1;i<=k;i++)
        tm[i]=-1;
    for(int i=0;i<N-1;i++)
    {
        g[H[i][0]].push_back(mp(H[i][1],L[i]));
        g[H[i][1]].push_back(mp(H[i][0],L[i]));
    }
    ans(0,-1);
    return tm[k];
}
/*
TEST1
4 3
0 1 1
1 2 2
1 3 4
2
TEST2
3 3
0 1 1
1 2 1
-1
TEST3
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'int centr(int, int)':
race.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'void dfsh(int, int, int, int)':
race.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfsm(int, int, int, int)':
race.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfsg(int, int, int)':
race.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'void ans(int, int)':
race.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[r].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[r].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[r].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:116:13: warning: unused variable 'dis' [-Wunused-variable]
         int dis=g[r][i].second;
             ^~~
race.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[r].size();i++)
                 ~^~~~~~~~~~~~

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