oj.uz

Submission #527063

# Submission time Handle Problem Language Result Execution time Memory
527063 2022-02-16T21:36:57 Z ThegeekKnight16 Race (IOI11_race) C++17
9 / 100
 145 ms 19400 KB 
#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;
}

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9688 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9688 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 6 ms 9688 KB Output is correct
12 Correct 5 ms 9696 KB Output is correct
13 Correct 6 ms 9696 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 5 ms 9636 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 6 ms 9676 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9688 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9688 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 6 ms 9688 KB Output is correct
12 Correct 5 ms 9696 KB Output is correct
13 Correct 6 ms 9696 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 5 ms 9636 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 6 ms 9676 KB Output is correct
19 Correct 5 ms 9712 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Incorrect 8 ms 9804 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9688 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9688 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 6 ms 9688 KB Output is correct
12 Correct 5 ms 9696 KB Output is correct
13 Correct 6 ms 9696 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 5 ms 9636 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 6 ms 9676 KB Output is correct
19 Correct 135 ms 19284 KB Output is correct
20 Correct 134 ms 19348 KB Output is correct
21 Incorrect 145 ms 19400 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9688 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9688 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 6 ms 9688 KB Output is correct
12 Correct 5 ms 9696 KB Output is correct
13 Correct 6 ms 9696 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 5 ms 9636 KB Output is correct
16 Correct 5 ms 9688 KB Output is correct
17 Correct 5 ms 9676 KB Output is correct
18 Correct 6 ms 9676 KB Output is correct
19 Correct 5 ms 9712 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Incorrect 8 ms 9804 KB Output isn't correct
22 Halted 0 ms 0 KB -