Submission #456210

#TimeUsernameProblemLanguageResultExecution timeMemory
456210sean617Race (IOI11_race)C++98
43 / 100
393 ms37996 KiB
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #define SZ 200005 #define A 1000005 #include "race.h" using namespace std; int n, k, mn, M = 1e9, s[A], sz[SZ]; bool v2[SZ]; vector<int> a[SZ], b[SZ]; queue<int> qu; int gs(int p, int q) { int i, t; sz[p] = 1; for (i = 0; i < a[p].size(); i++) { t = a[p][i]; if (t == q || v2[t]) continue; sz[p] += gs(t, p); } return sz[p]; } int gc(int p, int q, int nn) { int i, t; for (i = 0; i < a[p].size(); i++) { t = a[p][i]; if (t != q && !v2[t] && sz[t] *2 > nn) return gc(t, p, nn); } return p; } void g(int p, int q, int w, int cnt) { int i, t; if (w > k) return; mn = min(mn, cnt + s[k - w]); for (i = 0; i < a[p].size(); i++) { t = a[p][i]; if (t == q || v2[t]) continue; g(t, p, w + b[p][i], cnt + 1); } if (s[w] > cnt) { s[w] = cnt; qu.push(w); } } void f(int p) { int i, t, cen; gs(p, -1); cen = gc(p, -1, sz[p]); v2[cen] = 1; while (!qu.empty()) { t = qu.front(); qu.pop(); s[t] = M; } s[0] = 0; for (i = 0; i < a[cen].size(); i++) { t = a[cen][i]; if (v2[t]) continue; g(t, -1, b[cen][i], 1); } for (i = 0; i < a[cen].size(); i++) { t = a[cen][i]; if (v2[t]) continue; f(t); } } int best_path(int NN, int KK, int H[][2], int L[]) { int i, t1, t2, t3; n = NN; k = KK; for (i = 0; i < n - 1; i++) { t1 = H[i][0]; t2 = H[i][1]; t3 = L[i]; a[t1].push_back(t2); b[t1].push_back(t3); a[t2].push_back(t1); b[t2].push_back(t3); } mn = M; for (i = 0; i <= k; i++) s[i] = M; f(0); if (mn == M) mn = -1; return mn; }

Compilation message (stderr)

race.cpp: In function 'int gs(int, int)':
race.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'int gc(int, int, int)':
race.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'void g(int, int, int, int)':
race.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'void f(int)':
race.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (i = 0; i < a[cen].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~
race.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (i = 0; i < a[cen].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...