제출 #527063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527063		ThegeekKnight16	Race (IOI11_race)	C++17	9 / 100	145 ms	19400 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define INF 1000000010
using namespace std;

const int MAXN = 200010;
const int MAXK = 1000010;

vector<int> grafo[MAXN], pesos[MAXN];
int marc[MAXK], ultimo[MAXK], Sub[MAXN];
int MarcCentroid[MAXN];
int K;
int cnt = 0;

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 dfsSub(int v, int p)
{
  Sub[v] = 1;
  for (int i = 0; i < grafo[v].size(); i++)
  {
    int viz = grafo[v][i];
    if (viz == p) continue;
    if (MarcCentroid[viz]) continue;
    Sub[v] += dfsSub(viz, v);
  }
  return Sub[v];
}

int findCentroid(int v, int p, int n)
{
  for (int i = 0; i < grafo[v].size(); i++)
  {
    int viz = grafo[v][i];
    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;
  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;

    return min(acessa(K - dist) + prof, dfsTesta(viz, v, dist + peso, prof+1));
  }
  return (acessa(K - dist) + prof);
}

void dfsMuda(int v, int p, int dist, int prof)
{
  if (dist > K) return;
  muda(dist, min(acessa(dist), prof));
  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;
    dfsMuda(viz, v, dist + peso, prof+1);
  }
}

int divide_and_conquer(int v)
{
  zera();
  muda(0, 0);
  int N = dfsSub(v, v);
  int Centroid = findCentroid(v, v, N);

  MarcCentroid[Centroid] = 1;

  int resp = INF;
  for (int i = 0; i < grafo[Centroid].size(); i++)
  {
    int viz = grafo[Centroid][i];
    int peso = pesos[Centroid][i];
    if (MarcCentroid[viz]) continue;

    int Teste = dfsTesta(viz, Centroid, peso, 1);
    dfsMuda(viz, Centroid, peso, 1);

    resp = min(resp, Teste);
  }

  for (int i = 0; i < grafo[Centroid].size(); i++)
  {
    int viz = grafo[Centroid][i];
    if (MarcCentroid[viz]) continue;

    int Recur = divide_and_conquer(viz);

    resp = min(resp, Recur);
  }
  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 resposta = divide_and_conquer(1);
  if (resposta >= INF) return -1;
  return resposta;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int dfsSub(int, int)':
race.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int dfsTesta(int, int, int, int)':
race.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfsMuda(int, int, int, int)':
race.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int i = 0; i < grafo[v].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int divide_and_conquer(int)':
race.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i = 0; i < grafo[Centroid].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for (int i = 0; i < grafo[Centroid].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~

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