Submission #859763

#	Time	Username	Problem	Language	Result	Execution time	Memory
859763		vladburac	Race (IOI11_race)	C++17	0 / 100	5 ms	21104 KiB

race

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

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];
vector<int> centroidEdges[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;
}

struct Ancestor{
  ll sum;
  int length;
};
Ancestor anc[NMAX+1][MAXLOG+3];
int depth[NMAX+1];

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

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

map<ll, int> dp;
int ans = INF;

void dfs( int node, int i, int type, int k ) {
  ll sum = anc[node][depth[i]].sum;
  int length = anc[node][depth[i]].length;
  if( type == 0 && dp[k-sum] )
    ans = min( ans, dp[k-sum] + length );
  else if( type == 1 ) {
    if( dp[sum] )
      dp[sum] = min( dp[sum], length );
    else
      dp[sum] = length;
  }
  for( auto vec: centroidEdges[node] ) {
    if( vec != parent[node] )
      dfs( vec, i, type, k );
  }
}
int best_path( int n, int k, int h[][2], int len[] ) {
  int i;
  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, 0 );
  ans = INF;
  for( i = 0; i < n; i++ ) {
    dp.clear();
    for( auto vec: centroidEdges[i] ) {
      if( vec != parent[i] ) {
        dfs( vec, i, 0, k );
        dfs( vec, i, 1, k );
      }
    }
  }
  if( ans == INF )
    ans = -1;
  return ans;
}

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