Submission #526995

#	Time	Username	Problem	Language	Result	Execution time	Memory
526995		ThegeekKnight16	Race (IOI11_race)	C++17	9 / 100	143 ms	18556 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define debug(args...) //fprintf(stderr, args)
#define INF 1000000010
using namespace std;
const int MAXN = 200010;
vector<int> grafo[MAXN], pesos[MAXN];
int marc[1000010], ultimo[1000010], 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, int prof)
{
  if (dist > K) return INF;
  debug("\tmarc[%d]: %d, prof: %d, dist: %d\n",K - dist,acessa(K - dist),prof,dist);
  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(K - dist) == INF) return dfsTesta(viz, v, dist + peso, prof+1);
    return min(prof + acessa(K - dist), dfsTesta(viz, v, dist + peso, prof+1));
  }
  //if (acessa(K - dist) == INF) return INF;
  return prof + acessa(K - dist);
}

void dfsMarca(int v, int p, int dist, int prof)
{
  muda(dist, min(acessa(dist), prof));
  debug("\tmarc[%d]: %d, prof: %d, dist: %d\n",dist,acessa(dist),prof,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;
    dfsMarca(viz, v, dist + pesos[v][i], prof+1);
  }
}

int divide_and_conquer(int v, int p)
{
  zera();
  muda(0, 0);
  int n = dfsCentroid(v, p);
  int c = findCentroid(v, p, n);

  MarcCentroid[c] = 1;
  int resp = INF;
  debug("Centroid: %d\n",c);
  for (int i = 0; i < grafo[c].size(); i++)
  {
    int viz = grafo[c][i];
    int peso = pesos[c][i];
    if (MarcCentroid[viz]) continue;
    debug("\tviz: %d\n",viz);
    debug("\tTesta:\n");
    resp = min(resp, dfsTesta(viz, c, peso, 1));
    debug("\tMarca:\n");
    dfsMarca(viz, c, peso, 1);
  }

  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));
  }
  //debug("Centroid: %d, resp: %d\n",c,resp);
  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, int)':
race.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfsMarca(int, int, int, int)':
race.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int divide_and_conquer(int, int)':
race.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (int i = 0; i < grafo[c].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for (int i = 0; i < grafo[c].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~

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