Submission #526952

#	Time	Username	Problem	Language	Result	Execution time	Memory
526952		ar_paixaos19	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

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

int n, k, marc[MAXN], minl[MAXK], sub[MAXN], val[MAXN], prof[MAXN], ultimo[MAXK], cont = 0, resp;
vector<int> grafo[MAXN], peso[MAXN];

int acessa(int pos){
  if(ultimo[pos] == cont) return minl[pos];
  return INF + 10;
}

void muda(int pos, int valor){
  minl[pos] = valor;
  ultimo[pos] = cont;
  return;
}

void zera(){
  cont++;
  return;
}

void dfs1(int v, int p){
  //printf("X\n");
  sub[v] = 1;
  for(int i = 0; i < grafo[v].size(); i++){
    //printf("v = %d, p = %d\n", v, p);
    int viz = grafo[v][i];
    if(viz == p) continue;
    if(marc[viz] == 1) continue;
    dfs1(viz, v);
    sub[v] += sub[viz];
  }
  return;
}

void dfs2(int v, int p){
  //printf("Y\n");
  muda(val[v], min(acessa(val[v]), prof[v]));
  resp = min(resp, prof[v] + acessa(k - val[v]));
  for(int i = 0; i < grafo[v].size(); i++){
    int viz = grafo[v][i];
    if(viz == p) continue;
    if(marc[viz] == 1) continue;
    val[viz] = val[v] + peso[v][i];
    prof[viz] = prof[v] + 1;
    //printf("minl[%d] = %d\n", val[viz], acessa(val[viz]));
    dfs2(viz, v);
  }
  return;
}

int findcentroid(int v, int p){
  //printf("Z\n");
  for(int i = 0; i < grafo[v].size(); i++){
    int viz = grafo[v][i];
    if(viz == p) continue;
    if(marc[viz] == 1) continue;
    if(sub[viz] > n / 2) return findcentroid(viz, v);
  }
  return v;
}

int daq(int v, int p){
  dfs1(v, p);
  int centroid = findcentroid(v, p);
  marc[centroid] = 1;
  if(sub[centroid] == 1) return INF;
  zera();
  resp = INF;
  for(int i = 0; i < grafo[centroid].size(); i++){
    int viz = grafo[centroid][i];
    if(marc[viz] == 1) continue;
    val[viz] = peso[centroid][i];
    prof[viz] = 1;
    dfs2(viz, viz);
  }
  for(int i = 0; i < grafo[v].size(); i++){
    int viz = grafo[v][i];
    if(viz == p) continue;
    if(marc[viz] == 1) continue;
    resp = min(resp, daq(viz, v));
  }
  //printf("W\n");
  return resp;
}

int main(){
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n - 1; i++){
    int u, v, p; scanf("%d %d %d", &u, &v, &p);
    grafo[u].push_back(v); peso[u].push_back(p);
    grafo[v].push_back(u); peso[v].push_back(p);
    if(p > k){
      peso[u].pop_back();
      peso[v].pop_back();
    }
  }
  //printf("R\n");

  int resp;
  resp = daq(0, 0);
  if(resp == INF) resp = -1;
  printf("%d\n", resp);
  return 0;
}

Compilation message (stderr)

race.cpp: In function 'void dfs1(int, int)':
race.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int)':
race.cpp:45:20: 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 findcentroid(int, int)':
race.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int daq(int, int)':
race.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i < grafo[centroid].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d %d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:95:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     int u, v, p; scanf("%d %d %d", &u, &v, &p);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccTuQdBj.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccU4D9if.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccU4D9if.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status