#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;
}
vvi adj;
pi fr;
int diam = 0, cpos = 0;
int U = 0, V = 0, rU = 0, rV = 0;
vector<int> change_types;
int x = 0, actual_step = 0;
bool changed = false;
int send_message(int n, int i, int Pi) {
if (i <= 1) adj.assign(n+1, vi());
x = n - 30;
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);
U = fr.first; V = fr.second;
rU = U, rV = V;
} else if (step == 16) {
rV = V = furthest_from(U, n, adj);
}
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, V, adj) == cdiam ? 1 : 2); // if the diameter changed, did we switch u or v
change_types.push_back(type);
diam = cdiam;
if (type == 1) U = i;
else if (type == 2) V = i;
vi u12 = to_base(rU, 12, 4), v2 = to_base(rV, 2, 14);
if (step < 16 && !changed) {
if (type == 0) {
if (!((step % 4) == u12[step / 4] / 3)) return 0;
return 1 + (u12[step / 4] % 3);
} else {
if (type == 2) U = V;
changed = true;
return 4;
}
} else if (step < 16 && changed) {
if (!(step % 4 == 0 || step == 15)) return 0;
int ans = 4;
for (int k = 0; k < 4; k++) if (change_types[step - k] != 0) {ans = k; break;}
return ans;
} else if (step < 30) {
if (type == 0) {
return v2[min(13, step-16)];
} else if (type == 1) {
return v2[min(13, step-16)] + 2;
} else {
actual_step = 30;
return 4;
}
} else {
return type;
}
}
// 0 - no change, 1 - change u, 2 - change v
pi longest_path(vi S) {
int n = S.size();
int x = n - 30;
int u = 0, v = 0;
// for (int i = x; i < x+16; i+=4) {
// for (int j = i; j < i + 4; j++) cout << S[j];
// cout << " ";
// }
// cout << "\n";
int step = -1; bool changed = false;
for (int i = x; i < n; i++) {
step++;
if (step < 16 && !changed) {
if (S[i] == 4) {
// cout << "step: " << step << " changed\n";
u = i;
changed = true;
continue;
}
if (S[i] == 0) continue;
int p12 = pow(12, step / 4);
int v12 = 3 * (step % 4) + (S[i] - 1);
u += p12 * v12;
} else if (step < 16 && changed) {
if (!(step % 4 == 0 || step == 15)) continue;
if (S[i] == 4) continue;
u = i - S[i];
} else if (step < 30) {
if (S[i] == 4) {
step = 30;
v = i;
} else if (S[i] >= 2) {
u = i;
v += (S[i] - 2) * pow(2, step - 16);
} else {
v += S[i] * pow(2, step - 16);
}
} else {
if (S[i] == 1) {
u = i;
} else if (S[i] == 2) {
v = i;
}
}
}
// auto bp = furthest_pair(n, adj);
// if (!(dist_between(n, u, v, adj) == dist_between(n, bp.first, bp.second, adj))) {
// cout << "failure!\n";
// }
int A = u, B = v;
return {A, B};
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |