oj.uz

Submission #526995

# Submission time Handle Problem Language Result Execution time Memory
526995 2022-02-16T19:20:26 Z ThegeekKnight16 Race (IOI11_race) C++17
9 / 100
 143 ms 18556 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 7 ms 9648 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 5 ms 9620 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 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 4 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9676 KB Output is correct
12 Correct 5 ms 9692 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9692 KB Output is correct
16 Correct 6 ms 9700 KB Output is correct
17 Correct 5 ms 9692 KB Output is correct
18 Correct 6 ms 9740 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 9648 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 5 ms 9620 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 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 4 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9676 KB Output is correct
12 Correct 5 ms 9692 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9692 KB Output is correct
16 Correct 6 ms 9700 KB Output is correct
17 Correct 5 ms 9692 KB Output is correct
18 Correct 6 ms 9740 KB Output is correct
19 Correct 5 ms 9688 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Incorrect 6 ms 9816 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 9648 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 5 ms 9620 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 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 4 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9676 KB Output is correct
12 Correct 5 ms 9692 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9692 KB Output is correct
16 Correct 6 ms 9700 KB Output is correct
17 Correct 5 ms 9692 KB Output is correct
18 Correct 6 ms 9740 KB Output is correct
19 Correct 133 ms 18508 KB Output is correct
20 Correct 124 ms 18424 KB Output is correct
21 Incorrect 143 ms 18556 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 9648 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 5 ms 9620 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 9676 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 4 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 5 ms 9676 KB Output is correct
12 Correct 5 ms 9692 KB Output is correct
13 Correct 5 ms 9676 KB Output is correct
14 Correct 5 ms 9676 KB Output is correct
15 Correct 5 ms 9692 KB Output is correct
16 Correct 6 ms 9700 KB Output is correct
17 Correct 5 ms 9692 KB Output is correct
18 Correct 6 ms 9740 KB Output is correct
19 Correct 5 ms 9688 KB Output is correct
20 Correct 5 ms 9676 KB Output is correct
21 Incorrect 6 ms 9816 KB Output isn't correct
22 Halted 0 ms 0 KB -