Submission #672498

#	Time	Username	Problem	Language	Result	Execution time	Memory
672498		ToroTN	Race (IOI11_race)	C++14	100 / 100	504 ms	35736 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#define ll long long
#define pb push_back
#define X first
#define Y second
int n,ans=1e9,m,sz[200005],vis[200005],mn[1000005];
vector<pair<int,int> > v[200005];
void dfs_size(int u,int p)
{
    sz[u]=1;
    for(auto [node,w]:v[u])
    {
        if(vis[node]==0&&node!=p)
        {
            dfs_size(node,u);
            sz[u]+=sz[node];
        }
    }
}
int find_cen(int u,int p,int want)
{
    for(auto [node,w]:v[u])
    {
        if(node!=p&&vis[node]==0)
        {
            if(sz[node]>want)return find_cen(node,u,want);
        }
    }
    return u;
}
void compute(int u,int p,int type,int depth,int lv)
{
    //printf("%lld %lld %lld %lld %lld\n",u,p,type,depth,lv);
    if(depth>m)return;
    if(type==1)
    {
        ans=min(ans,lv+mn[m-depth]);
    }else if(type==0)
    {
        mn[depth]=min(mn[depth],lv);
    }else
    {
        mn[depth]=1e9,mn[m-depth]=1e9;
    }
    for(auto [node,w]:v[u])
    {
        if(node!=p&&vis[node]==0)compute(node,u,type,depth+w,lv+1);
    }
}
void centroid(int u)
{
    dfs_size(u,u);
    int cen=find_cen(u,u,sz[u]/2);
    //printf("cen=%d\n",cen);
    vis[cen]=1;
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)compute(node,node,2,w,1);
    }
    mn[0]=0;
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            //printf("node=%lld\n",node);
            compute(node,node,1,w,1);
            /*for(int i=0;i<=m;i++)
            {
                printf("%lld ",mn[i]);
            }
            printf("\n");*/
            compute(node,node,0,w,1);
            /*for(int i=0;i<=m;i++)
            {
                printf("%lld ",mn[i]);
            }
            printf("\n");*/
        }
    }
    //printf("\n");
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            centroid(node);
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",vis[i]);
    }
    printf("\n");*/
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,m=K;
    for(int i=0;i<n-1;i++)
    {
        v[H[i][0]+1].pb({H[i][1]+1,L[i]});
        v[H[i][1]+1].pb({H[i][0]+1,L[i]});
    }
    // for(int i=1;i<=n;i++)
    // {
    //     printf("i=%d\n",i);
    //     for(auto [node,w]:v[i])
    //     {
    //         printf("%d %d\n",node,w);
    //     }
    //     printf("\n");
    // }
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<=1000000;i++)mn[i]=1e9;
    centroid(1);
    if(ans==1e9)return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs_size(int, int)':
race.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'void compute(int, int, int, int, int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'void centroid(int)':
race.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto [node,w]:v[cen])
      |              ^

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