Submission #755111

#	Time	Username	Problem	Language	Result	Execution time	Memory
755111		amin	Race (IOI11_race)	C++14	9 / 100	205 ms	20720 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,int>ma[100000];
int pa[100000];
int dist[100000];
int k;
ll val[100000];
int sz[100000];
int ans=1000000;
int par(int x)
{
    if(pa[x]==x)
        return x;
    pa[x]=par(pa[x]);
    return pa[x];
}
int un(int x,int y,ll desired)
{
    int sum=1000000;
    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(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(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<int>v[100000],w[100000];
void dfs(int in,int pa)
{
    for(int y=0;y<v[in].size();y++)
    {
        int i=v[in][y];
        int h=w[in][y];
        if(i==pa)
            continue;
            dist[i]=dist[in]+1;
            val[i]=val[in]+h;
        dfs(i,in);
    }

}
void solve(int in,int pa)
{

    ma[in][val[in]]=dist[in];
   // cout<<dist[in]<<endl;
    int z=1000000;
    for(auto i:v[in])
    {
        if(i==pa)
            continue;
        solve(i,in);
        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[])
{
    int n=N;
   k=K;

  for(int i=0;i<n;i++)
  {
    int x=H[i][0];
    int 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(int i=0;i<n;i++)
  {
      pa[i]=i;
      sz[i]=1;
  }

solve(0,0);/*
for(int 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>n)
    return -1;
else
return ans;
}

Compilation message (stderr)

race.cpp: In function 'int un(int, 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: In function 'void dfs(int, int)':
race.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int y=0;y<v[in].size();y++)
      |                 ~^~~~~~~~~~~~~
race.cpp:61:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |         if(i==pa)
      |         ^~
race.cpp:63:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |             dist[i]=dist[in]+1;
      |             ^~~~

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