Submission #71632

#	Time	Username	Problem	Language	Result	Execution time	Memory
71632		MANcity	Race (IOI11_race)	C++14	43 / 100	3061 ms	36564 KiB

race

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "race.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int K;
vector<vector<pair<int,int> > > G(200002);
int sizeVer[200002];
int used[200002];
int sumSize;
int verNum;
int ka[5000002];
int ANSWER=1000000;
void dfs(int v,int p)
{
    if(G[v].size()==1 && G[v][0].first==p)
        sizeVer[v]=1;
    else
        sizeVer[v]=0;
    for0(j,G[v].size()-1)
    {
        int to=G[v][j].first;
        if(to!=p && used[to]==0)
        {
            dfs(to,v);
            sizeVer[v]+=sizeVer[to];
        }
    }
    verNum++;
    sizeVer[v]+=1;
    sumSize+=sizeVer[v];
}
int find_centr(int v,int p)
{
    int u=0;
    for0(j,G[v].size()-1)
    {
        int to=G[v][j].first;
        if(to!=p && used[to]==0)
        {
            if(2*sizeVer[to]>verNum)
            {
                u=1;
                return find_centr(to,v);
            }
        }
    }
    if(u==0)
        return v;
}
int update_dfs(int v,int p,int len,int qan)
{
    if(ka[len]==-1)
        ka[len]=qan;
    else
        ka[len]=min(qan,ka[len]);
    if(K>=len)
    for0(j,G[v].size()-1)
    {
        int to=G[v][j].first;
        int l=G[v][j].second;
        if(to!=p && used[to]==0)
        {
            update_dfs(to,v,len+l,qan+1);
        }
    }
}
int stug_dfs(int v,int p,int len,int qan)
{
    if(K>=len)
    {
        //cout<<v<<" AAAA "<<len<<" "<<K-len<<" "<<ka[K-len]<<endl;
        if(ka[K-len]!=-1)
        {
            ANSWER=min(ANSWER,ka[K-len]+qan);
            //cout<<v<<" "<<len<<" "<<ANSWER<<endl;
        }
    }
    if(K>=len)
    for0(j,G[v].size()-1)
    {
        int to=G[v][j].first;
        int l=G[v][j].second;
        if(to!=p && used[to]==0)
        {
            stug_dfs(to,v,len+l,qan+1);
        }
    }
}
void solve(int v)
{
    for0(i,K)
        ka[i]=-1;
    ka[0]=0;
    sumSize=0;
    verNum=0;
    dfs(v,-1);
    if(verNum==1)
        return;
    int centr=find_centr(v,-1);
    //cout<<v<<" "<<centr<<endl;
    for0(i,G[centr].size()-1)
    {
        int to=G[centr][i].first;
        int len=G[centr][i].second;
        if(used[to]==0)
        {
            stug_dfs(to,centr,len,1);
            update_dfs(to,centr,len,1);
        }
    }
    used[centr]=1;
    for0(i,G[centr].size()-1)
    {
        int to=G[centr][i].first;
        if(used[to]==0)
        {
            solve(to);
        }
    }
}
int best_path(int N, int K_0, int H[][2], int L[])
{
    K=K_0;
    for0(i,N-2)
    {
        G[H[i][0]].pb({H[i][1],L[i]});
        G[H[i][1]].pb({H[i][0],L[i]});
    }
    solve(1);
    if(ANSWER==1000000)
        return -1;
    return ANSWER;
}
/*
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
*/
/*
6 16
0 1 10
0 2 1
2 3 2
3 4 3
2 5 4
4
*/

Compilation message (stderr)

race.cpp: In function 'int update_dfs(int, int, int, int)':
race.cpp:85:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int stug_dfs(int, int, int, int)':
race.cpp:107:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int find_centr(int, int)':
race.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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