Submission #526950

#	Time	Username	Problem	Language	Result	Execution time	Memory
526950		ThegeekKnight16	Race (IOI11_race)	C++14	0 / 100	6 ms	9688 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define INF 1000000010
using namespace std;
const int MAXN = 200010;
vector<int> grafo[MAXN], pesos[MAXN];
int marc[MAXN], ultimo[MAXN], sub[MAXN];
int MarcCentroid[MAXN];
int cnt = 0;
int K;

int acessa(int pos)
{
  if (ultimo[pos] ==  cnt) return marc[pos];
  return INF;
}

void muda(int pos, int val)
{
  marc[pos] = val;
  ultimo[pos] = cnt;
}

void zera(){cnt++;}

int dfsCentroid(int v, int p)
{
  sub[v] = 1;
  for (auto viz : grafo[v])
  {
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    sub[v] += dfsCentroid(viz, v);
  }
  return sub[v];
}

int findCentroid(int v, int p, int n)
{
  for (auto viz : grafo[v])
  {
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    if (sub[viz] > n / 2) return findCentroid(viz, v, n);
  }
  return v;
}

int dfsTesta(int v, int p, int dist)
{
  if (dist > K) return INF;
  for (int i = 0; i < grafo[v].size(); i++)
  {
    int viz = grafo[v][i];
    int peso = pesos[v][i];
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    if (acessa(dist) == INF || acessa(K - dist) == INF) return dfsTesta(viz, v, dist + peso);
    return min(acessa(dist) + acessa(K - dist), dfsTesta(viz, v, dist + peso));
  }
  if (acessa(dist) == INF || acessa(K - dist) == INF) return INF;
  return acessa(dist) + acessa(K - dist);
}

void dfsMarca(int v, int p, int dist)
{
  for (int i = 0; i < grafo[v].size(); i++)
  {
    int viz = grafo[v][i];
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    if (dist + pesos[v][i] > K) continue;
    if (acessa(dist + pesos[v][i]) > acessa(dist) + 1 || acessa(dist + pesos[v][i]) == INF) muda(dist + pesos[v][i], acessa(dist) + 1);
    dfsMarca(viz, v, dist + pesos[v][i]);
  }
}

int divide_and_conquer(int v, int p)
{
  zera();
  int n = dfsCentroid(v, p);
  int c = findCentroid(v, p, n);
  if (p == -1) p = c;

  MarcCentroid[c] = 1;
  int resp = INF;
  for (int i = 0; i < grafo[c].size(); i++)
  {
    int viz = grafo[c][i];
    int peso = pesos[c][i];
    if (MarcCentroid[viz]) continue;
    muda(peso, 1);
    resp = min(resp, dfsTesta(viz, c, peso));
    dfsMarca(viz, c, peso);
  }

  for (int i = 0; i < grafo[c].size(); i++)
  {
    int viz = grafo[c][i];
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    resp = min(resp, divide_and_conquer(viz, c));
  }
  return resp;
}

int best_path(int n, int k, int edges[][2], int cost[])
{
  int N = n; K = k;
  for (int i = 0; i < N-1; i++)
  {
    int X, Y, P;
    X = edges[i][0];
    Y = edges[i][1];
    P = cost[i];
    grafo[X].push_back(Y);
    pesos[X].push_back(P);
    grafo[Y].push_back(X);
    pesos[Y].push_back(P);
  }
  int resp = divide_and_conquer(1, 1);
  if (resp >= INF) return -1;
  else return resp;
}

Compilation message (stderr)

race.cpp: In function 'int dfsTesta(int, int, int)':
race.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfsMarca(int, int, int)':
race.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int divide_and_conquer(int, int)':
race.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i = 0; i < grafo[c].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = 0; i < grafo[c].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~

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