| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1190636 | mehmetkagan | Tropical Garden (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30; // since 2^30 > 1e9
const int MAXN = 150005;
int N, M, P;
vector<int> adj[MAXN];
map<pair<int, int>, int> beauty; // ((u,v) -> beauty index)
int best[MAXN][2]; // best[u][0] = best neighbor, best[u][1] = 2nd best
int nxt[MAXN][MAXN]; // nxt[cur][prev] = deterministic next
int dp[LOG][MAXN][MAXN]; // dp[i][cur][prev] = number of ways to reach P in 2^i steps
void count_routes(int n, int m, int p, int R[][2], int q, int G[]) {
N = n; M = m; P = p;
// Build graph
for (int i = 0; i < M; ++i) {
int u = R[i][0], v = R[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
beauty[{u, v}] = i;
beauty[{v, u}] = i;
}
// Compute best and second-best neighbors
for (int u = 0; u < N; ++u) {
sort(adj[u].begin(), adj[u].end(), [&](int a, int b) {
return beauty[{u, a}] < beauty[{u, b}];
});
best[u][0] = adj[u][0];
best[u][1] = adj[u].size() > 1 ? adj[u][1] : -1;
}
// Build next[cur][prev]
for (int cur = 0; cur < N; ++cur) {
for (int prev = 0; prev < N; ++prev) {
if (best[cur][0] != prev)
nxt[cur][prev] = best[cur][0];
else if (best[cur][1] != -1)
nxt[cur][prev] = best[cur][1];
else
nxt[cur][prev] = prev;
}
}
// Base case: dp[0][cur][prev] = 1 if next move ends at P
for (int cur = 0; cur < N; ++cur) {
for (int prev = 0; prev < N; ++prev) {
int next = nxt[cur][prev];
if (next == P) dp[0][cur][prev] = 1;
}
}
// Binary lifting
for (int k = 1; k < LOG; ++k) {
for (int cur = 0; cur < N; ++cur) {
for (int prev = 0; prev < N; ++prev) {
int mid = nxt[cur][prev];
int nxtp = nxt[mid][cur];
dp[k][cur][prev] = dp[k-1][mid][cur] + dp[k-1][cur][prev]; // or use mod if needed
nxt[cur][prev] = nxt[nxt[cur][prev]][cur];
}
}
}
// Answer queries
for (int i = 0; i < q; ++i) {
int K = G[i];
long long res = 0;
for (int start = 0; start < N; ++start) {
for (int to : adj[start]) {
int cur = to, prev = start;
long long cnt = 1;
for (int k = 0; k < LOG; ++k) {
if ((K >> k) & 1) {
cnt = dp[k][cur][prev];
tie(cur, prev) = make_pair(nxt[cur][prev], cur);
}
}
if (cur == P) res += cnt;
}
}
answer(res);
}
}