Pagini recente » Monitorul de evaluare | Istoria paginii runda/simulare_oni9/clasament | Diferente pentru calibrare-limite-de-timp intre reviziile 94 si 221 | Diferente pentru calibrare-limite-de-timp intre reviziile 88 si 221 | Cod sursa (job #2258756)
#include <bits/stdc++.h>
#define x first
#define y second
#define MAXN 32000
#define LOG 16
#define INF 10000000
std::vector <int> g[MAXN + 1];
int lvl[MAXN + 1];
void dfs(int nod) {
for(auto it:g[nod]) {
lvl[it] = lvl[nod] + 1;
dfs(it);
}
}
int rmq[2 * MAXN + 2][LOG + 1];
int lg[2 * MAXN + 2];
int poz[MAXN + 1];
int ne;
void Euler(int nod) {
ne++;
rmq[ne][0] = nod;
poz[nod] = ne;
for(auto it:g[nod]) {
Euler(it);
ne++;
rmq[ne][0] = nod;
}
}
inline void prec() {
for(int i = 2; i <= ne; i++)
lg[i] = lg[i / 2] + 1;
}
inline void make_rmq() {
prec();
for(int p2 = 1; (1 << p2) <= ne; p2++)
for(int i = 1; i + (1 << p2) <= ne + 1; i++)
if(lvl[rmq[i][p2 - 1]] < lvl[rmq[i + (1 << (p2 - 1))][p2 - 1]])
rmq[i][p2] = rmq[i][p2 - 1];
else
rmq[i][p2] = rmq[i + (1 << (p2 - 1))][p2 - 1];
}
inline int get_lca(int x, int y){
int a = poz[x];
int b = poz[y];
if(a > b)
std::swap(a , b);
int p2 = lg[b - a + 1];
if(lvl[rmq[a][p2]] < lvl[rmq[b - (1 << p2) + 1][p2]])
return rmq[a][p2];
return rmq[b - (1 << p2) + 1][p2];
}
int dp[MAXN + 1][LOG + 1];
int v[MAXN + 1][LOG + 1];
inline void make_dp(int n) {
for(int p2 = 1; (1 << p2) <= n; p2++)
for(int i = 1; i <= n; i++) {
dp[i][p2] = std::min(dp[i][p2 - 1] , dp[v[i][p2 - 1]][p2 - 1]);
v[i][p2] = v[v[i][p2 - 1]][p2 - 1];
}
}
inline int solve(int x, int y) {
int l = lvl[x] - lvl[y], nod = x;
int ans = INF;
for(int i = LOG; i >= 0; i--)
if(l >= (1 << i)) {
l -= (1 << i);
ans = std::min(ans , dp[nod][i]);
nod = v[nod][i];
}
return ans;
}
std::pair <int , int> qry;
inline std::pair <int , int> next_qry(int x, int y, int a, int b, int c, int d, int n,int z) {
return std::make_pair((x * a + y * b) % n + 1 , (y * c + z * d) % n + 1);
}
int main(){
std::ifstream fin("atac.in");
std::ofstream fout("atac.out");
int i, n, m, p;
std::ios::sync_with_stdio(false);
fin >> n >> m >> p;
for(i = 2; i <= n; i++) {
int x, val;
fin >> x >> val;
g[x].push_back(i);
v[i][0] = x;
dp[i][0] = val;
}
lvl[1] = 1;
dfs(1);
Euler(1);
make_rmq();
make_dp(n);
int a, b, c, d;
fin >> qry.x >> qry.y >> a >> b >> c >> d;
for(i = 1; i <= m; i++) {
int lca = get_lca(qry.x , qry.y);
int ans = std::min(solve(qry.x , lca) , solve(qry.y , lca));
if(ans == INF)
ans = 0;
if(i > m - p)
fout << ans << std::endl;
qry = next_qry(qry.x, qry.y, a, b, c, d, n, ans);
}
fin.close();
fout.close();
return 0;
}