Submission #908756

#	Time	Username	Problem	Language	Result	Execution time	Memory
908756		uped	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2e5;

ll n, k;
vector<pair<int, ll>> adj[MAX];
int sz[MAX];
bool removed[MAX];

int get_size(int n, int p = -1) {
  sz[n] = 1;
  for (auto& [x, _] : adj[n]){
    if (removed[x] || x == p) continue;
    sz[n] += get_size(x, n);
  }
  return sz[n];
}

int find_centroid(int desired, int n, int p = -1) {
  for (auto& [x, _] : adj[n]) {
    if (removed[x] || x == p) continue;
    if (sz[x] > desired) return find_centroid(desired, x, n);
  }
  return n;
}

int best = 1e9;
const int MAX_K = 1e6;
int m[MAX_K + 1];
vector<int> touched;

void solve(int n, int p, int d, ll l, bool filling) {
  if (d > best || l > k) return;
  if (filling) {
    if (m[l] != -1) {
      m[l] = min(m[l], d);
    } else {
      m[l] = d;
    }
    touched.push_back(l);
  } else {
    if (m[k - l] != -1) {
      best = min(best, d + m[k - l]);
    }
  }
  for (auto& [x, w] : adj[n]) {
    if (removed[x] || x == p) continue;
    solve(x, n, d + 1, l + w, filling);
  }
}

void decompose(int n) {
  int c = find_centroid(get_size(n) / 2, n);
  removed[c] = true;

  int start = touched.size();
  m[0] = 0;
  for (auto& [x, w] : adj[c]) {
    solve(x, c, 1, w, false);
    solve(x, c, 1, w, true);
  }
  for (int i = start; i < touched.size(); ++i) {
    m[touched[i]] = -1;
  }
  //touched.clear();

  for (auto& [x, _] : adj[c]) {
    if (removed[x]) continue;
    decompose(x);
  }
}


int best_path(int N, int K, int H[][2], int L[])
{
  touched.reserve(4000000);
  memset(m, -1, sizeof(m));
  n = N;
  k = K;
  for (int i = 0; i < n - 1; ++i) {
    int w = L[i];
    int a = H[i][0], b = H[i][1];
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
  }
  decompose(0);
  if (best == 1e9) {
    return -1;
  } else {
    return best;
  }
}

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2e5;

ll n, k;
vector<pair<int, ll>> adj[MAX];
int sz[MAX];
bool removed[MAX];

int get_size(int n, int p = -1) {
  sz[n] = 1;
  for (auto& [x, _] : adj[n]){
    if (removed[x] || x == p) continue;
    sz[n] += get_size(x, n);
  }
  return sz[n];
}

int find_centroid(int desired, int n, int p = -1) {
  for (auto& [x, _] : adj[n]) {
    if (removed[x] || x == p) continue;
    if (sz[x] > desired) return find_centroid(desired, x, n);
  }
  return n;
}

int best = 1e9;
const int MAX_K = 1e6;
int m[MAX_K + 1];
vector<int> touched;

void solve(int n, int p, int d, ll l, bool filling) {
  if (d > best || l > k) return;
  if (filling) {
    if (m[l] != -1) {
      m[l] = min(m[l], d);
    } else {
      m[l] = d;
    }
    touched.push_back(l);
  } else {
    if (m[k - l] != -1) {
      best = min(best, d + m[k - l]);
    }
  }
  for (auto& [x, w] : adj[n]) {
    if (removed[x] || x == p) continue;
    solve(x, n, d + 1, l + w, filling);
  }
}

void decompose(int n) {
  int c = find_centroid(get_size(n) / 2, n);
  removed[c] = true;

  int start = touched.size();
  m[0] = 0;
  for (auto& [x, w] : adj[c]) {
    solve(x, c, 1, w, false);
    solve(x, c, 1, w, true);
  }
  for (int i = start; i < touched.size(); ++i) {
    m[touched[i]] = -1;
  }
  //touched.clear();

  for (auto& [x, _] : adj[c]) {
    if (removed[x]) continue;
    decompose(x);
  }
}


int best_path(int N, int K, int H[][2], int L[])
{
  touched.reserve(4000000);
  memset(m, -1, sizeof(m));
  n = N;
  k = K;
  for (int i = 0; i < n - 1; ++i) {
    int w = L[i];
    int a = H[i][0], b = H[i][1];
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
  }
  decompose(0);
  if (best == 1e9) {
    return -1;
  } else {
    return best;
  }
}

Compilation message (stderr)

race.cpp: In function 'void decompose(int)':
race.cpp:65:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i = start; i < touched.size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~
race.cpp: At global scope:
race.cpp:102:11: error: redefinition of 'const int MAX'
  102 | const int MAX = 2e5;
      |           ^~~
race.cpp:6:11: note: 'const int MAX' previously defined here
    6 | const int MAX = 2e5;
      |           ^~~
race.cpp:104:4: error: redefinition of 'll n'
  104 | ll n, k;
      |    ^
race.cpp:8:4: note: 'll n' previously declared here
    8 | ll n, k;
      |    ^
race.cpp:104:7: error: redefinition of 'll k'
  104 | ll n, k;
      |       ^
race.cpp:8:7: note: 'll k' previously declared here
    8 | ll n, k;
      |       ^
race.cpp:105:23: error: redefinition of 'std::vector<std::pair<int, long long int> > adj [200000]'
  105 | vector<pair<int, ll>> adj[MAX];
      |                       ^~~
race.cpp:9:23: note: 'std::vector<std::pair<int, long long int> > adj [200000]' previously declared here
    9 | vector<pair<int, ll>> adj[MAX];
      |                       ^~~
race.cpp:106:5: error: redefinition of 'int sz [200000]'
  106 | int sz[MAX];
      |     ^~
race.cpp:10:5: note: 'int sz [200000]' previously declared here
   10 | int sz[MAX];
      |     ^~
race.cpp:107:6: error: redefinition of 'bool removed [200000]'
  107 | bool removed[MAX];
      |      ^~~~~~~
race.cpp:11:6: note: 'bool removed [200000]' previously declared here
   11 | bool removed[MAX];
      |      ^~~~~~~
race.cpp:109:5: error: redefinition of 'int get_size(int, int)'
  109 | int get_size(int n, int p = -1) {
      |     ^~~~~~~~
race.cpp:13:5: note: 'int get_size(int, int)' previously defined here
   13 | int get_size(int n, int p = -1) {
      |     ^~~~~~~~
race.cpp:118:5: error: redefinition of 'int find_centroid(int, int, int)'
  118 | int find_centroid(int desired, int n, int p = -1) {
      |     ^~~~~~~~~~~~~
race.cpp:22:5: note: 'int find_centroid(int, int, int)' previously defined here
   22 | int find_centroid(int desired, int n, int p = -1) {
      |     ^~~~~~~~~~~~~
race.cpp:126:5: error: redefinition of 'int best'
  126 | int best = 1e9;
      |     ^~~~
race.cpp:30:5: note: 'int best' previously defined here
   30 | int best = 1e9;
      |     ^~~~
race.cpp:127:11: error: redefinition of 'const int MAX_K'
  127 | const int MAX_K = 1e6;
      |           ^~~~~
race.cpp:31:11: note: 'const int MAX_K' previously defined here
   31 | const int MAX_K = 1e6;
      |           ^~~~~
race.cpp:128:5: error: redefinition of 'int m [1000001]'
  128 | int m[MAX_K + 1];
      |     ^
race.cpp:32:5: note: 'int m [1000001]' previously declared here
   32 | int m[MAX_K + 1];
      |     ^
race.cpp:129:13: error: redefinition of 'std::vector<int> touched'
  129 | vector<int> touched;
      |             ^~~~~~~
race.cpp:33:13: note: 'std::vector<int> touched' previously declared here
   33 | vector<int> touched;
      |             ^~~~~~~
race.cpp:131:6: error: redefinition of 'void solve(int, int, int, ll, bool)'
  131 | void solve(int n, int p, int d, ll l, bool filling) {
      |      ^~~~~
race.cpp:35:6: note: 'void solve(int, int, int, ll, bool)' previously defined here
   35 | void solve(int n, int p, int d, ll l, bool filling) {
      |      ^~~~~
race.cpp:151:6: error: redefinition of 'void decompose(int)'
  151 | void decompose(int n) {
      |      ^~~~~~~~~
race.cpp:55:6: note: 'void decompose(int)' previously defined here
   55 | void decompose(int n) {
      |      ^~~~~~~~~
race.cpp: In function 'void decompose(int)':
race.cpp:161:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |   for (int i = start; i < touched.size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~
race.cpp: At global scope:
race.cpp:173:5: error: redefinition of 'int best_path(int, int, int (*)[2], int*)'
  173 | int best_path(int N, int K, int H[][2], int L[])
      |     ^~~~~~~~~
race.cpp:77:5: note: 'int best_path(int, int, int (*)[2], int*)' previously defined here
   77 | int best_path(int N, int K, int H[][2], int L[])
      |     ^~~~~~~~~