Submission #251120

#	Time	Username	Problem	Language	Result	Execution time	Memory
251120		uacoder123	Race (IOI11_race)	C++14	0 / 100	14 ms	16128 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int vis[200001]={},vis1[200001]={},sz[200001],vis2[200001];
map<int,int> m[200001];
vector<ii> al[200001];
int n,k,ans=200001,co=0;
void dfs(int node)
{
  co++;
  vis1[node]=1;
  //cout<<node<<endl;
  sz[node]=1;
  for(int i=0;i<al[node].size();++i)
  {
    if(vis[al[node][i].F]+vis1[al[node][i].F]==0)
    {
      dfs(al[node][i].F);
      sz[node]+=sz[al[node][i].F];
    }
  }
}
int tell(int node,int p,int to)
{
  for(int i=0;i<al[node].size();++i)
    if(vis[al[node][i].F]==0&&al[node][i].F!=p&&sz[al[node][i].F]>to/2)
      return(tell(al[node][i].F,node,to));
  return(node);
}
void dfs1(int node,int root,int upa,int dis,int e)
{
  vis2[node]=1;
  if(upa!=-1)
  {
    if(m[upa].find(dis)==m[upa].end())
      m[upa][dis]=e;
    else
      m[upa][dis]=min(m[upa][dis],e);
  }
  int f=-1;
  for(int i=0;i<al[node].size();++i)
  {
    if(vis[al[node][i].F]+vis2[al[node][i].F]==0)
    {
      if(root==node)
      {
        f=al[node][i].F;
        dfs1(al[node][i].F,root,al[node][i].F,dis+al[node][i].S,e+1);
        m[al[node][i].F][0]=0;
      }
      else
        dfs1(al[node][i].F,root,upa,dis+al[node][i].S,e+1);
    }
  }
  if(node==root)
  {
    for(int i=0;i<al[node].size();++i)
    {
    //  cout<<f<<' '<<al[node][i].F<<endl;
      if(f==al[node][i].F||vis[al[node][i].F]==1)
        continue;
      for(auto j=(m[al[node][i].F].begin());j!=m[al[node][i].F].end();++j)
      {
        if((*j).F>k)
          break;
        if(m[f].find(k-(*j).F)!=m[f].end())
          ans=min(ans,m[f][k-(*j).F]+(*j).S);
      }
      for(auto j=(m[al[node][i].F].begin());j!=m[al[node][i].F].end();++j)
      {
        if(m[f].find((*j).F)==m[f].end())
          m[f][(*j).F]=(*j).S;
        else
          m[f][(*j).F]=min(m[f][(*j).F],(*j).S);
      }
    }
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  n=N;
  k=K;
  int c=0;
  for(int i=0;i<n-1;++i)
  {
    al[H[i][0]].pb(mp(H[i][1],L[i]));
    al[H[i][1]].pb(mp(H[i][0],L[i]));
  }
  while(c!=n)
  {
    for(int i=0;i<n;++i)
    {
      if(vis[i]+vis1[i]==0)
      {
      //  cout<<"hi "<<i<<' '<<vis1[i]<<endl;
        dfs(i);
        int cen=tell(i,i,sz[i]);
        vis[cen]=1;
        //cout<<i<<cen<<endl;
        dfs1(cen,cen,-1,0,0);
        c++;
      }
    }
  //  cout<<ans<<"Masti"<<endl;
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
  }
  if(ans==200001)
    return(-1);
  return(ans);
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
race.cpp: In function 'int tell(int, int, int)':
race.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int, int, int, int)':
race.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
race.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<al[node].size();++i)
                 ~^~~~~~~~~~~~~~~~

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