Submission #29410

#	Time	Username	Problem	Language	Result	Execution time	Memory
29410		kavun	Race (IOI11_race)	C++14	21 / 100	3056 ms	13432 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
bool mk[200010];
int n,k;
vii adj[200010];
int sub[200010];
int ans = 1e9;


int subsize(int v, int par)
{
  int sum = 0;
  for(int i = 0; i < adj[v].size(); i++)
    if(adj[v][i].first != par && !mk[adj[v][i].first])
      sum += subsize(adj[v][i].first,v);

  sub[v] = sum + 1;
  return sum + 1;
}

int centroid(int v, int par)
{
  for(int i = 0; i < adj[v].size(); i++)
    if(adj[v][i].first != par && !mk[adj[v][i].first])
      {
	int u = adj[v][i].first;
	if(sub[u] > n/2)
	  return centroid(u,v);
      }
  return v;
}

void dfs(int v, int par, int d, int len, map<int,int>& m)
{
  if(len > k)
    return;
  if(m.find(len) != m.end())
    m[len] = min(m[len],d);
  else 
    m[len] = d;
  for(int i = 0; i < adj[v].size(); i++)
    {
      int u = adj[v][i].first;
      int l = adj[v][i].second;
      if(u != par && !mk[u])
	dfs(u,v,d+1,len + l, m);
    }
}

void solveForCen(int v)
{
  map<int,int> mp;
  mp[0] = 0;
  for(int i = 0;i < adj[v].size(); i++)
    {
      if(!mk[adj[v][i].first])
	{
	  map<int,int> m;
	  int u = adj[v][i].first;
	  dfs(u,v,1,adj[v][i].second,m);
	  for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
	    {
	      int len = it->first;
	      if(mp.find(k - len) != mp.end())
		ans = min(ans,m[len] + mp[k - len]);
	    }
	  for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
	    {
	      int len = it->first;
	      if(mp.find(len) != mp.end())
		mp[len] = min(mp[len],m[len]);
	      else
		mp[len] = m[len];
	    }
	}
    }
}

int solve(int v)
{
  subsize(v,v);
  int cen = centroid(v,v);
  mk[cen] = true;
  solveForCen(cen);
  for(int i = 0; i < adj[cen].size(); i++)
    {
      int u = adj[cen][i].first;
      if(!mk[u])
	solve(u);
    }
}



int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for(int i = 0; i < N -1; i++)
    {
      int v = H[i][0],u = H[i][1],l = L[i];
      adj[v].pb(ii(u,l));
      adj[u].pb(ii(v,l));
    }

  solve(0);
  if(ans == 1e9)
    return -1;
  else 
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int subsize(int, int)':
race.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, std::map<int, int>&)':
race.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[v].size(); i++)
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void solveForCen(int)':
race.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i < adj[v].size(); i++)
                 ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int solve(int)':
race.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[cen].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~
race.cpp:96:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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