Submission #859657

#	Time	Username	Problem	Language	Result	Execution time	Memory
859657		vladburac	Race (IOI11_race)	C++17	0 / 100	3 ms	14680 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
const int NMAX = 2e5;
const int INF = 1e9;

int parent[NMAX+1];
bool is_removed[NMAX+1];
int sz[NMAX+1];
vector <pair<ll, int>> distSubtree[NMAX+1];
vector <pair<int, int>> edges[NMAX+1];

int calcSize( int node, int parent ) {
  sz[node] = 1;
  for( auto vec: edges[node] ) {
    if( vec.first != parent && !is_removed[vec.first] )
      sz[node] += calcSize( vec.first, node );
  }
  return sz[node];
}

int find_centroid( int node, int parent, int totalSz ) {
  for( auto vec: edges[node] ) {
    if( vec.first != parent && !is_removed[vec.first] && sz[vec.first] > totalSz / 2 )
      return find_centroid( vec.first, node, totalSz );
  }
  return node;
}

void updDist( int init, int node, int parent, int depth, ll sumEdges ) {
  distSubtree[init].push_back( { sumEdges, depth } );
  for( auto vec: edges[node] ) {
    if( !is_removed[vec.first] && vec.first != parent )
      updDist( init, vec.first, node, depth + 1, sumEdges + vec.second );
  }
}

void decomposition( int node, int centroidParent ) {
  int totalSz = calcSize( node, -1 );
  int centroid = find_centroid( node, -1, totalSz );
  is_removed[centroid] = true;
  parent[centroid] = centroidParent;
  updDist( centroid, centroid, -1, 0, 0 );
  for( auto vec: edges[centroid] ) {
    //cout << vec.first << " ";
    if( !is_removed[vec.first] )
      decomposition( vec.first, centroid );
  }
}

int best_path( int n, int k, int h[][2], int len[] ) {
  int i, st, dr, ans, mini, j, ind;
  for( i = 0; i < n - 1; i++ ) {
    edges[h[i][0]].push_back( { h[i][1], len[i] } );
    edges[h[i][1]].push_back( { h[i][0], len[i] } );
  }
  decomposition( 0, -1 );
  ans = INF;
  for( i = 0; i < n; i++ ) {
    sort( distSubtree[i].begin(), distSubtree[i].end(), [&]( pair<ll, int>& a, pair<ll, int>& b ) {
         return a.first < b.first;
    } );
    ind = 0;
    mini = INF;
    for( j = 0; j < distSubtree[i].size() - 1; j++ ) {
      mini = min( mini, distSubtree[i][j].second );
      if( distSubtree[i][j].first != distSubtree[i][j+1].first ) {
        distSubtree[i][ind++] = { distSubtree[i][j].first, mini };
        mini = INF;
      }
    }
    mini = min( mini, distSubtree[i][j].second );
    distSubtree[i][ind++] = { distSubtree[i][j].first, mini };
    st = 0;
    dr = ind - 1;
    while( st < dr ) {
      while( distSubtree[i][st].first + distSubtree[i][dr].first > k )
        dr--;
      if( distSubtree[i][st].first + distSubtree[i][dr].first == k && st != dr )
        ans = min( ans, distSubtree[i][st].second + distSubtree[i][dr].second );
      st++;
    }
  }
  if( ans == INF )
    ans = -1;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for( j = 0; j < distSubtree[i].size() - 1; j++ ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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