Submission #672474

#	Time	Username	Problem	Language	Result	Execution time	Memory
672474		ToroTN	Race (IOI11_race)	C++14	0 / 100	7 ms	12756 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
ll n,ans=1e9,m,sz[200005],vis[200005],mn[1000005];
vector<pair<ll,ll> > v[200005];
void dfs_size(ll u,ll p)
{
    sz[u]=1;
    for(auto [node,w]:v[u])
    {
        if(vis[node]==0&&node!=p)
        {
            dfs_size(node,u);
            sz[u]+=sz[node];
        }
    }
}
ll find_cen(ll u,ll p,ll 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(ll u,ll p,ll type,ll depth,ll 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;
    }
    for(auto [node,w]:v[u])
    {
        if(node!=p&&vis[node]==0)compute(node,u,type,depth+w,lv+1);
    }
}
void centroid(ll u)
{
    dfs_size(u,u);
    ll cen=find_cen(u,u,sz[u]/2);
    //printf("cen=%lld\n",cen);
    vis[cen]=1;
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)compute(u,u,2,w,1);
    }
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            compute(u,u,1,w,1);
            compute(u,u,0,w,1);
        }
    }
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            centroid(node);
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%lld ",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("%lld %lld\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(long long int, long long 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 'long long int find_cen(long long int, long long int, long long 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(long long int, long long int, long long int, long long int, long long int)':
race.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'void centroid(long long int)':
race.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [node,w]:v[cen])
      |              ^

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