Submission #790901

#TimeUsernameProblemLanguageResultExecution timeMemory
790901atomRace (IOI11_race)C++17
Compilation error
0 ms0 KiB
#include "bits/stdc++.h" // @JASPER'S BOILERPLATE using namespace std; using ll = long long; using ull = unsigned long long; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define REP(i, b) for(int i = 0; i < b; i++) #define PER(i, b) for(int i = b - 1; i >= 0; i--) #define fi first #define se second #define all(x) x.begin(),x.end() #ifdef JASPER2 #include "debug.h" #else #define debug(...) 166 #endif using pii = pair < int, int >; const ll LINF = 1e18 + 5; const int INF = 1e9; const int MOD = 1e9 + 7; const int MAX = 2e5 + 5; int n, k; vector <pii> adj[MAX]; int cnt[MAX * 5]; int sz[MAX]; bool vis[MAX]; int Tsize = 0; void reSubsize(int u, int p) { sz[u] = 1; for (auto &[w, v] : adj[u]) { if (v != p && !vis[v]) { reSubsize(v, u); sz[u] += sz[v]; } } } int getCentroid(int u, int p) { for (auto &[w, v] : adj[u]) if (v != p && !vis[v] && sz[v] > Tsize / 2) return getCentroid(v, u); return u; } int f[MAX * 5]; // f(i) : Minimum edge to form i length from subtree to current centroid (0 in sub; int maxW, ans; void process(int u, int p, int eCnt, int W) { if (W > k) return; ans = min(ans, eCnt + f[k - W]); maxW = max(maxW, W); for (auto &[w, v] : adj[u]) { if (v != p && !vis[v]) { process(v, u, eCnt + 1, W + w); } } f[W] = min(f[W], eCnt); } void decompose(int u, int p) { reSubsize(u, 0); Tsize = sz[u]; int x = getCentroid(u, 0); // cnt[0] = 1; f[0] = 0; vis[x] = 1; maxW = 0; // debug(u, Tsize, x); vector <pii> valid; for (auto [w, v] : adj[x]) { if (!vis[v]) { process(v, x, 1, w); valid.push_back({w, v}); // debug(v); // FOR(i, 1, n) { // debug(f[i]); // } } } for (int i = 0; i <= maxW; ++i) f[i] = INF; for (auto [w, v] : valid) { decompose(v, x); } } int best_path(int N, int K, int a[][2], int W[]) { cin >> n >> k; n = N, k = K; for (int i = 0; i < n; ++i) { int u = a[i][0], v = a[i][1], w = W[i]; ++u, ++v; adj[u].push_back({w, v}); adj[v].push_back({w, u}); } ans = INF; for (int i = 0; i < MAX * 5; ++i) f[i] = INF; decompose(1, 0); if (ans == INF) ans = -1; return ans; } void run_case() { int N, K; int H[N][2]; int L[N]; best_path(N,K,H,L); } signed main() { cin.tie(0) -> sync_with_stdio(0); #ifdef JASPER2 freopen("in1", "r", stdin); #endif int Test = 1; //cin >> Test; for (int test = 1; test <= Test; test++){ run_case(); } }

Compilation message (stderr)

race.cpp: In function 'void run_case()':
race.cpp:112:15: warning: 'N' is used uninitialized in this function [-Wuninitialized]
  112 |     int H[N][2];
      |               ^
race.cpp:114:14: warning: 'K' is used uninitialized in this function [-Wuninitialized]
  114 |     best_path(N,K,H,L);
      |     ~~~~~~~~~^~~~~~~~~
/usr/bin/ld: /tmp/ccSqdJBj.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccs5lC7k.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status