Submission #1262451

#TimeUsernameProblemLanguageResultExecution timeMemory
1262451madamadam3Migrations (IOI25_migrations)C++20
72.89 / 100
49 ms1728 KiB
#include "migrations.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; using pi = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; void dfs(int u, int p, vi &dist, vvi &adj) { for (auto &v : adj[u]) { if (v == p) continue; dist[v] = dist[u] + 1; dfs(v, u, dist, adj); } } int furthest_from(int u, int n, vvi &adj) { vector<int> dist(n); dfs(u, u, dist, adj); int f = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f]) f = i; return f; } int dist_between(int n, int u, int v, vvi &adj) { vector<int> dist(n); dfs(u, u, dist, adj); return dist[v]; } pi furthest_pair(int n, vvi &adj) { vector<int> dist(n); dfs(0, 0, dist, adj); int f1 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f1]) f1 = i; dist = vi(n, 0); dfs(f1, f1, dist, adj); int f2 = 0; for (int i = 0; i < n; i++) if (dist[i] > dist[f2]) f2 = i; return {min(f1, f2), max(f1, f2)}; } vi to_base(ll A, ll b, int pad = 0) { vi ans; while (A > 0LL) { ans.push_back(A % b); A /= b; } while (ans.size() < pad) ans.push_back(0); return ans; } ll from_base(vi bx, ll b) { ll po = 1; ll ans = 0; for (auto &el : bx) { ans += ll(el) * po; po *= b; } return ans; } string test_switch(vi codes) { vector<pi> switches; for (int i = 0; i < int(codes.size()); i++) if (codes[i] != 0) switches.push_back({i+2, codes[i] - 1}); int A = 0, B = 1; int L = 1; for (auto &el : switches) { int w = el.first; if (el.second) { (L == A ? B : A) = w; } else { (L == A ? A : B) = w; } L = w; } return "(" + to_string(A) + "," + to_string(B) + ")"; } vector<bool> bsearch(int x) { // record decision log of binary search to find x vector<bool> log; int lo = 0, hi = 10000; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (mid < x) { log.push_back(true); lo = mid + 1; } else { hi = mid; log.push_back(false); } } return log; } vvi adj; pi fr; int diam = 0, prev_change = 0, cpos = 0; vector<int> change_types; vector<int> diam_history; int x = 0, actual_step = 0; int send_message(int n, int i, int Pi) { if (i <= 1) adj.assign(n+1, vi()); x = n - 28; adj[Pi].push_back(i); adj[i].push_back(Pi); if (i < x) return 0; int step = actual_step++; if (step == 0) {fr = furthest_pair(n, adj); diam = dist_between(n, fr.first, fr.second, adj); prev_change = fr.first;} pi cfr = furthest_pair(n, adj); int u = cfr.first, v = cfr.second; int cdiam = dist_between(n, u, v, adj); int type = cdiam == diam ? 0 : (dist_between(n, i, prev_change, adj) == cdiam ? 2 : 1); diam = cdiam; prev_change = type == 0 ? prev_change : i; int ans = step < 14 ? min(1, fr.first & (1 << step)) : min(1, fr.second & (1 << (step - 14))); if (type == 0) return ans; else if (type == 1) return ans + 2; else {actual_step--; return 4;} } // 0 - no change, 1 - cur replaces prev, 2 - cur connects to prev pi longest_path(vi S) { int n = S.size(); int x = n - 28; int u = 0, v = 0; vector<pi> switches; // idx, 0 if extension, 1 if connection int step = 0; for (int i = x; i < n; i++) { if (S[i] == 4) { switches.push_back({i, 1}); continue; } int value = S[i]; if (S[i] >= 2) { switches.push_back({i, 0}); value -= 2; } if (step < 14) u |= value << step; else v |= value << (step - 14); step++; } int A = u, B = v; int L = u; for (auto &el : switches) { int w = el.first; if (el.second) { // joining (L == A ? B : A) = w; } else { // extending (L == A ? A : B) = w; } L = w; } return {A, B}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...