Submission #1251372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251372		k1r1t0	Migrations (IOI25_migrations)	C++20	97.45 / 100	32 ms	1324 KiB

migrations

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 11000;
const int LOGN = 20;

int n, jmp[N][LOGN], par[N], dep[N], d1, d2, d1l, d1r, d2l, d2r, qq[N];

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if (dep[u] - (1 << k) >= dep[v])
			u = jmp[u][k];
	if (u == v) return v;
	for (int k = LOGN - 1; k >= 0; k--)
		if (jmp[u][k] != jmp[v][k])
			u = jmp[u][k], v = jmp[v][k];
	return jmp[u][0];
}

int dist(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void add(int v, int p) {
	par[v] = p;
	jmp[v][0] = p;
	dep[v] = dep[p] + 1;
	for (int k = 1; k < LOGN; k++)
		jmp[v][k] = jmp[jmp[v][k - 1]][k - 1];
}

void upd_diam(int v) {
	if (dist(d1, d2) < dist(v, d2)) d1 = v;
	if (dist(d1, d2) < dist(d1, v)) d2 = v;
}

vector<int> lens = {9094, 768, 96, 24, 8, 4, 2}; // 4 in the end
int ptr = 0, last = -1;

bool check(int u, int v) {
	return (u == d1 && v == d2) || (u == d2 && v == d1);
}

int send_message(int N, int i, int p) {
	if (i == 1) {
		d1l = d2l = 0;
		d1r = d2r = lens[0] - 1;
		n = N;
		for (int i = 0; i < n; i++)
			qq[i] = 0;
	}
	add(i, p);
	upd_diam(i);
	while (ptr < (int) lens.size() && last < i) {
		last += lens[ptr];
		ptr++;
	}
	if (i == last && ptr > 1) {
		int prv = lens[ptr - 2];
		int cur = lens[ptr - 1];
		int mx = (prv + cur - 1) / cur;
		int d1v = (d1r < d1 ? 0 : (d1 - d1l) / cur + 1);
		int d2v = (d2r < d2 ? 0 : (d2 - d2l) / cur + 1);
		if (d1v == 0) {
			d1l = i - cur + 1, d1r = i;
		} else {
			d1l += (d1v - 1) * cur;
			d1r = d1l + cur - 1;
		}
		if (d2v == 0) {
			d2l = i - cur + 1, d2r = i;
		} else {
			d2l += (d2v - 1) * cur;
			d2r = d2l + cur - 1;
		}
		int val = d1v * (mx + 1) + d2v;
		if (val != 0) {
			int put = (val - 1) % 4 + 1;
			int pos = (val - 1) / 4 + i;
			qq[pos] = put;
		}
	}
	if (i >= n - 3) {
		int a = d1l, b = d1r, c = d2l, d = d2r;
		int e = n - 4, f = n - 3, g = n - 2, h = n - 1;
		if (i == n - 3) {
			if (check(e, f)) qq[i] = 0;
			if (check(a, c) || check(a, d)) qq[i] = 1;
			if (check(b, c) || check(b, d)) qq[i] = 2;
			if (check(a, e) || check(b, e) || check(c, e) || check(d, e)) qq[i] = 3;
			if (check(a, f) || check(b, f) || check(c, f) || check(d, f)) qq[i] = 4;
		}
		if (i == n - 2) {
			if (qq[n - 3] == 0) {
				if (check(e, f)) qq[i] = 0;
				if (check(e, g)) qq[i] = 1;
				if (check(f, g)) qq[i] = 2;
			}
			if (qq[n - 3] == 1) {
				if (check(a, c)) qq[i] = 0;
				if (check(a, d)) qq[i] = 1;
				if (check(a, g)) qq[i] = 2;
				if (check(c, g)) qq[i] = 3;
				if (check(d, g)) qq[i] = 4;
			}
			if (qq[n - 3] == 2) {
				if (check(b, c)) qq[i] = 0;
				if (check(b, d)) qq[i] = 1;
				if (check(b, g)) qq[i] = 2;
				if (check(c, g)) qq[i] = 3;
				if (check(d, g)) qq[i] = 4;
			}
			if (qq[n - 3] == 3) {
				if (check(e, g)) qq[i] = 0;
				if (check(a, e) || check(b, e)) qq[i] = 1;
				if (check(c, e) || check(d, e)) qq[i] = 2;
				if (check(a, g) || check(b, g)) qq[i] = 3;
				if (check(c, g) || check(d, g)) qq[i] = 4;
			}
			if (qq[n - 3] == 4) {
				if (check(f, g)) qq[i] = 0;
				if (check(a, f) || check(b, f)) qq[i] = 1;
				if (check(c, f) || check(d, f)) qq[i] = 2;
				if (check(a, g) || check(b, g)) qq[i] = 3;
				if (check(c, g) || check(d, g)) qq[i] = 4;
			}
		}
		if (i == n - 1) {
			if (qq[n - 3] == 0) {
				if (qq[n - 2] == 0) {
					if (check(e, f)) qq[n - 1] = 0;
					if (check(e, h)) qq[n - 1] = 1;
					if (check(f, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 1) {
					if (check(e, g)) qq[n - 1] = 0;
					if (check(e, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 2) {
					if (check(f, g)) qq[n - 1] = 0;
					if (check(f, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
			}
			if (qq[n - 3] == 1) {
				if (qq[n - 2] == 0) {
					if (check(a, c)) qq[n - 1] = 0;
					if (check(a, h)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 1) {
					if (check(a, d)) qq[n - 1] = 0;
					if (check(a, h)) qq[n - 1] = 1;
					if (check(d, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 2) {
					if (check(a, g)) qq[n - 1] = 0;
					if (check(a, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 3) {
					if (check(c, g)) qq[n - 1] = 0;
					if (check(c, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 4) {
					if (check(d, g)) qq[n - 1] = 0;
					if (check(d, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
			}
			if (qq[n - 3] == 2) {
				if (qq[n - 2] == 0) {
					if (check(b, c)) qq[n - 1] = 0;
					if (check(b, h)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 1) {
					if (check(b, d)) qq[n - 1] = 0;
					if (check(b, h)) qq[n - 1] = 1;
					if (check(d, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 2) {
					if (check(b, g)) qq[n - 1] = 0;
					if (check(b, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 3) {
					if (check(c, g)) qq[n - 1] = 0;
					if (check(c, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 4) {
					if (check(d, g)) qq[n - 1] = 0;
					if (check(d, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
			}
			if (qq[n - 3] == 3) {
				if (qq[n - 2] == 0) {
					if (check(e, g)) qq[n - 1] = 0;
					if (check(e, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 1) {
					if (check(a, e)) qq[n - 1] = 0;
					if (check(b, e)) qq[n - 1] = 1;
					if (check(a, h)) qq[n - 1] = 2;
					if (check(b, h)) qq[n - 1] = 3;
					if (check(e, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 2) {
					if (check(c, e)) qq[n - 1] = 0;
					if (check(d, e)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
					if (check(d, h)) qq[n - 1] = 3;
					if (check(e, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 3) {
					if (check(a, g)) qq[n - 1] = 0;
					if (check(b, g)) qq[n - 1] = 1;
					if (check(a, h)) qq[n - 1] = 2;
					if (check(b, h)) qq[n - 1] = 3;
					if (check(g, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 4) {
					if (check(c, g)) qq[n - 1] = 0;
					if (check(d, g)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
					if (check(d, h)) qq[n - 1] = 3;
					if (check(g, h)) qq[n - 1] = 4;
				}
			}
			if (qq[n - 3] == 4) {
				if (qq[n - 2] == 0) {
					if (check(f, g)) qq[n - 1] = 0;
					if (check(f, h)) qq[n - 1] = 1;
					if (check(g, h)) qq[n - 1] = 2;
				}
				if (qq[n - 2] == 1) {
					if (check(a, f)) qq[n - 1] = 0;
					if (check(b, f)) qq[n - 1] = 1;
					if (check(a, h)) qq[n - 1] = 2;
					if (check(b, h)) qq[n - 1] = 3;
					if (check(f, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 2) {
					if (check(c, f)) qq[n - 1] = 0;
					if (check(d, f)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
					if (check(d, h)) qq[n - 1] = 3;
					if (check(f, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 3) {
					if (check(a, g)) qq[n - 1] = 0;
					if (check(b, g)) qq[n - 1] = 1;
					if (check(a, h)) qq[n - 1] = 2;
					if (check(b, h)) qq[n - 1] = 3;
					if (check(g, h)) qq[n - 1] = 4;
				}
				if (qq[n - 2] == 4) {
					if (check(c, g)) qq[n - 1] = 0;
					if (check(d, g)) qq[n - 1] = 1;
					if (check(c, h)) qq[n - 1] = 2;
					if (check(d, h)) qq[n - 1] = 3;
					if (check(g, h)) qq[n - 1] = 4;
				}
			}
		}
	}
	if (i >= n - 3) {
		srand(i);
		return (qq[i] + rand()) % 5;
	}
	return qq[i];
}

pair<int, int> longest_path(vector<int> S) {
	n = S.size();
	d1l = d2l = 0;
	d1r = d2r = lens[0] - 1;
	for (int i = 0; i < n; i++)
		qq[i] = S[i];
	for (int i = n - 3; i <= n - 1; i++) {
		srand(i);
		qq[i] = (qq[i] - rand() % 5 + 5) % 5;
	}
	for (int i = 1; i < n; i++) {
		while (ptr < (int) lens.size() && last < i) {
			last += lens[ptr];
			ptr++;
		}
		if (i == last && ptr > 1) {
			int prv = lens[ptr - 2];
			int cur = lens[ptr - 1];
			int mx = (prv + cur - 1) / cur;
			int nxt = (ptr == (int) lens.size() ? 2 : lens[ptr - 0]);
			int lst = i + nxt - 1;
			int put = -1, pos = -1;
			for (int j = i; j <= lst; j++)
				if (qq[j] != 0) {
					pos = j;
					put = qq[j];
				}
			int val = 0;
			if (put != -1)
				val = (pos - i) * 4 + put;
			int d1v = val / (mx + 1);
			int d2v = val % (mx + 1);
			if (d1v == 0) {
				d1l = i - cur + 1, d1r = i;
			} else {
				d1l += (d1v - 1) * cur;
				d1r = d1l + cur - 1;
			}
			if (d2v == 0) {
				d2l = i - cur + 1, d2r = i;
			} else {
				d2l += (d2v - 1) * cur;
				d2r = d2l + cur - 1;
			}
		}
	}
	int a = d1l, b = d1r, c = d2l, d = d2r;
	int e = n - 4, f = n - 3, g = n - 2, h = n - 1;
	if (qq[n - 3] == 0) {
		if (qq[n - 2] == 0) {
			if (qq[n - 1] == 0) return {e, f};
			if (qq[n - 1] == 1) return {e, h};
			if (qq[n - 1] == 2) return {f, h};
		}
		if (qq[n - 2] == 1) {
			if (qq[n - 1] == 0) return {e, g};
			if (qq[n - 1] == 1) return {e, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 2) {
			if (qq[n - 1] == 0) return {f, g};
			if (qq[n - 1] == 1) return {f, h};
			if (qq[n - 1] == 2) return {g, h};
		}
	}
	if (qq[n - 3] == 1) {
		if (qq[n - 2] == 0) {
			if (qq[n - 1] == 0) return {a, c};
			if (qq[n - 1] == 1) return {a, h};
			if (qq[n - 1] == 2) return {c, h};
		}
		if (qq[n - 2] == 1) {
			if (qq[n - 1] == 0) return {a, d};
			if (qq[n - 1] == 1) return {a, h};
			if (qq[n - 1] == 2) return {d, h};
		}
		if (qq[n - 2] == 2) {
			if (qq[n - 1] == 0) return {a, g};
			if (qq[n - 1] == 1) return {a, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 3) {
			if (qq[n - 1] == 0) return {c, g};
			if (qq[n - 1] == 1) return {c, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 4) {
			if (qq[n - 1] == 0) return {d, g};
			if (qq[n - 1] == 1) return {d, h};
			if (qq[n - 1] == 2) return {g, h};
		}
	}
	if (qq[n - 3] == 2) {
		if (qq[n - 2] == 0) {
			if (qq[n - 1] == 0) return {b, c};
			if (qq[n - 1] == 1) return {b, h};
			if (qq[n - 1] == 2) return {c, h};
		}
		if (qq[n - 2] == 1) {
			if (qq[n - 1] == 0) return {b, d};
			if (qq[n - 1] == 1) return {b, h};
			if (qq[n - 1] == 2) return {d, h};
		}
		if (qq[n - 2] == 2) {
			if (qq[n - 1] == 0) return {b, g};
			if (qq[n - 1] == 1) return {b, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 3) {
			if (qq[n - 1] == 0) return {c, g};
			if (qq[n - 1] == 1) return {c, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 4) {
			if (qq[n - 1] == 0) return {d, g};
			if (qq[n - 1] == 1) return {d, h};
			if (qq[n - 1] == 2) return {g, h};
		}
	}
	if (qq[n - 3] == 3) {
		if (qq[n - 2] == 0) {
			if (qq[n - 1] == 0) return {e, g};
			if (qq[n - 1] == 1) return {e, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 1) {
			if (qq[n - 1] == 0) return {a, e};
			if (qq[n - 1] == 1) return {b, e};
			if (qq[n - 1] == 2) return {a, h};
			if (qq[n - 1] == 3) return {b, h};
			if (qq[n - 1] == 4) return {e, h};
		}
		if (qq[n - 2] == 2) {
			if (qq[n - 1] == 0) return {c, e};
			if (qq[n - 1] == 1) return {d, e};
			if (qq[n - 1] == 2) return {c, h};
			if (qq[n - 1] == 3) return {d, h};
			if (qq[n - 1] == 4) return {e, h};
		}
		if (qq[n - 2] == 3) {
			if (qq[n - 1] == 0) return {a, g};
			if (qq[n - 1] == 1) return {b, g};
			if (qq[n - 1] == 2) return {a, h};
			if (qq[n - 1] == 3) return {b, h};
			if (qq[n - 1] == 4) return {g, h};
		}
		if (qq[n - 2] == 4) {
			if (qq[n - 1] == 0) return {c, g};
			if (qq[n - 1] == 1) return {d, g};
			if (qq[n - 1] == 2) return {c, h};
			if (qq[n - 1] == 3) return {d, h};
			if (qq[n - 1] == 4) return {g, h};
		}
	}
	if (qq[n - 3] == 4) {
		if (qq[n - 2] == 0) {
			if (qq[n - 1] == 0) return {f, g};
			if (qq[n - 1] == 1) return {f, h};
			if (qq[n - 1] == 2) return {g, h};
		}
		if (qq[n - 2] == 1) {
			if (qq[n - 1] == 0) return {a, f};
			if (qq[n - 1] == 1) return {b, f};
			if (qq[n - 1] == 2) return {a, h};
			if (qq[n - 1] == 3) return {b, h};
			if (qq[n - 1] == 4) return {f, h};
		}
		if (qq[n - 2] == 2) {
			if (qq[n - 1] == 0) return {c, f};
			if (qq[n - 1] == 1) return {d, f};
			if (qq[n - 1] == 2) return {c, h};
			if (qq[n - 1] == 3) return {d, h};
			if (qq[n - 1] == 4) return {f, h};
		}
		if (qq[n - 2] == 3) {
			if (qq[n - 1] == 0) return {a, g};
			if (qq[n - 1] == 1) return {b, g};
			if (qq[n - 1] == 2) return {a, h};
			if (qq[n - 1] == 3) return {b, h};
			if (qq[n - 1] == 4) return {g, h};
		}
		if (qq[n - 2] == 4) {
			if (qq[n - 1] == 0) return {c, g};
			if (qq[n - 1] == 1) return {d, g};
			if (qq[n - 1] == 2) return {c, h};
			if (qq[n - 1] == 3) return {d, h};
			if (qq[n - 1] == 4) return {g, h};
		}
	}
	assert(false);
}














































#ifdef LOCAL
int main() {
	freopen("01.in", "r", stdin);
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> P(N, 0);
  for (int i = 1; i < N; ++i) {
    assert(1 == scanf("%d", &P[i]));
  }

  std::vector<int> S(N, 0);
  for (int i = 1; i < N; ++i) {
    S[i] = send_message(N, i, P[i]);
  }
  for (int i = 1; i < N; ++i) {
    printf("%d%c", S[i], " \n"[i + 1 == N]);
  }

  auto [U, V] = longest_path(S);
  printf("%d %d\n", U, V);
  fclose(stdout);

  return 0;
}
#endif

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 67.4511 / 70