Submission #755302

#	Time	Username	Problem	Language	Result	Execution time	Memory
755302		amin	Race (IOI11_race)	C++14	100 / 100	815 ms	86416 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,ll>ma[200000];
ll pa[200000];
ll dist[200000];
ll k;
ll val[200000];
ll sz[200000];
ll ans=10000000000;
ll par(ll x)
{
    if(pa[x]==x)
        return x;
    pa[x]=par(pa[x]);
    return pa[x];
}
ll un(ll x,ll y,ll desired)
{
    ll sum=100000000000000;
    x=par(x);
    y=par(y);
    if(x==y)
        return sum;
    if(sz[y]>sz[x])
        swap(x,y);
        pa[y]=x;
        sz[x]+=sz[y];
        sz[y]=0;
     //   cout<<sz[x]<<endl;
    for(auto i:ma[y])
    {
      //  cout<<desired-i.first<<endl;
      if(i.second==0)
        continue;
        if(ma[x][desired-i.first]!=0)//beware of the root case
        {
         //   cout<<1<<endl;

            sum=min(sum,i.second+ma[x][desired-i.first]);
        }


    }for(auto i:ma[y])
    {
if(i.second==0)
    continue;
if(ma[x][i.first]==0)
    ma[x][i.first]=i.second;
else
        ma[x][i.first]=min(i.second,ma[x][i.first]);
    }
    ma[y].clear();
    return sum;
}
vector<ll>v[200000],w[200000];
void dfs(ll in,ll pa)
{
    for(ll y=0;y<v[in].size();y++)
    {
        ll i=v[in][y];
        ll h=w[in][y];
        if(i==pa)
            continue;
            dist[i]=dist[in]+1;
            val[i]=val[in]+h;
        dfs(i,in);
    }

}
void solve(ll in,ll pa)
{

    ma[in][val[in]]=dist[in];
   // cout<<dist[in]<<endl;
    ll z=10000000000;
    for(auto i:v[in])
    {
        if(i==pa)
            continue;
        solve(i,in);
        //z=min(z,un(in,i,k+2*(val[in])));



    }
    for(auto i:v[in])
    {
        if(i==pa)
            continue;

        z=min(z,un(in,i,k+2*(val[in])));



    }

   // cout<<in<<' '<<z<<endl;
    ans=min(ans,z-2*dist[in]);
}
int best_path(int N, int K, int H[][2], int L[])
{
    ll n=N;
   k=K;

  for(ll i=0;i<n;i++)
  {
    ll x=H[i][0];
    ll y=H[i][1];
    v[x].push_back(y);
    v[y].push_back(x);
    w[x].push_back(L[i]);
    w[y].push_back(L[i]);
  }
  dist[0]=1;
  dfs(0,0);
  for(ll i=0;i<n;i++)
  {
      pa[i]=i;
      sz[i]=1;
  }

solve(0,0);/*
for(ll i=0;i<n;i++)
{
   // cout<<ma[i].size()<<' '<<sz[i];
    for(auto z:ma[i])
    {
        cout<<z.first<<' '<<z.second<<endl;
    }

}
cout<<endl;
cout<<ans<<endl;*/
if(ans>1000000)
    return -1;
else
return ans;
}

Compilation message (stderr)

race.cpp: In function 'long long int un(long long int, long long int, long long int)':
race.cpp:26:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |     if(sz[y]>sz[x])
      |     ^~
race.cpp:28:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |         pa[y]=x;
      |         ^~
race.cpp:35:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   35 |       if(i.second==0)
      |       ^~
race.cpp:37:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |         if(ma[x][desired-i.first]!=0)//beware of the root case
      |         ^~
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:60:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(ll y=0;y<v[in].size();y++)
      |                ~^~~~~~~~~~~~~
race.cpp:64:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   64 |         if(i==pa)
      |         ^~
race.cpp:66:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |             dist[i]=dist[in]+1;
      |             ^~~~

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