Submission #526964

#	Time	Username	Problem	Language	Result	Execution time	Memory
526964		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;
int h[MAXN][2], l[MAXN];
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 best_path(int n, int k, int h[][2], int l[]){
  for(int i = 0; i < n - 1; i++){
    grafo[h[i][0]].push_back(h[i][1]); peso[h[i][0]].push_back(l[i]);
    grafo[h[i][1]].push_back(h[i][0]); peso[h[i][1]].push_back(l[i]);
    if(l[i] > k){
      peso[h[i][0]].pop_back();
      peso[h[i][1]].pop_back();
    }
  }
  int resp = daq(0, 0);
  if(resp == INF) resp = -1;
  return resp;
}

int main(){
  scanf("%d %d", &n, &k);
  for(int i = 0; i < n - 1; i++){
    int u, v, p; scanf("%d %d %d", &u, &v, &p);
    h[i][0] = u; h[i][1] = v; l[i] = p;
  }
  //printf("R\n");
  printf("%d\n", best_path(n, k, h, l));
  return 0;
}

Compilation message (stderr)

race.cpp: In function 'void dfs1(int, int)':
race.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int)':
race.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int findcentroid(int, int)':
race.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int daq(int, int)':
race.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 0; i < grafo[centroid].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0; i < grafo[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   scanf("%d %d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     int u, v, p; scanf("%d %d %d", &u, &v, &p);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc4lKg27.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVlQWE7.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status