Pagini recente » Cod sursa (job #1824384) | Cod sursa (job #3321558) | Cod sursa (job #2194560) | Cod sursa (job #1434362) | Cod sursa (job #3331545)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
#if 0
#define int ll
#define uint ull
#endif
/**
* Problem: Atac
* URL: https://infoarena.ro/problema/atac
* TL: 400 ms
* ML: 64 MB
*
* Good Luck!
*/
void preinit() {
}
const int LOG_MAX = 16;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> up, mn;
vector<int> depth;
void dfs(int nod, int tt = 0) {
for (auto x : adj[nod]) {
if (x.first != tt) {
depth[x.first] = depth[nod] + 1;
up[0][x.first] = nod;
mn[0][x.first] = x.second;
dfs(x.first, nod);
}
}
}
void tc() {
int n, m, p;
cin >> n >> m >> p;
adj.resize(n + 1);
depth.resize(n + 1);
up.resize(LOG_MAX, vector<int>(n + 1));
mn.resize(LOG_MAX, vector<int>(n + 1, INT32_MAX));
for (int i = 2; i <= n; i++) {
int u, v;
cin >> u >> v;
adj[i].push_back({u, v});
adj[u].push_back({i, v});
// cout << i << " " << u << " " << v << '\n';
}
// cout << '\n';
dfs(1);
// for (int i = 0; i < 2; i++) {
// for (int j = 1; j <= n; j++) {
// cout << up[i][j] << " ";
// }
// cout << '\n';
// }
// cout << '\n';
// for (int i = 0; i < 2; i++) {
// for (int j = 1; j <= n; j++) {
// cout << mn[i][j] << " ";
// }
// cout << '\n';
// }
// cout << '\n';
for (int i = 1; i < LOG_MAX; i++) {
for (int j = 1; j <= n; j++) {
up[i][j] = up[i - 1][up[i - 1][j]];
mn[i][j] = min(mn[i - 1][up[i - 1][j]], mn[i - 1][j]);
}
}
auto query = [&](int u, int v) -> int {
int ans = INT32_MAX;
if (depth[u] < depth[v])
swap(u, v);
for (int i = LOG_MAX - 1; i >= 0; i--) {
if (depth[u] > depth[v]) {
if ((1 << i) <= depth[u] - depth[v]) {
ans = min(ans, mn[i][u]);
u = up[i][u];
}
} else if (u != v) {
if (up[i][u] != up[i][v]) {
ans = min({ans, mn[i][u], mn[i][v]});
u = up[i][u];
v = up[i][v];
}
} else
return ans;
}
return min({ans, mn[0][u], mn[0][v]});
};
int x, y, a, b, c, d;
cin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= m; i++) {
int z = query(x, y);
if (i >= m - p + 1) {
cout << z << '\n';
}
int xx = (x * a + y * b) % n + 1, yy = (y * c + z * d) % n + 1;
x = xx;
y = yy;
}
}
#define MTC 0
#define FIO 1
#define FN "atac"
signed main() {
#if FIO == 1 && !defined(LOCAL)
(void)freopen(FN ".in", "r", stdin);
(void)freopen(FN ".out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
preinit();
#if MTC == 1
signed tt;
cin >> tt;
while (tt--) tc();
#else
tc();
#endif
return 0;
}