Pagini recente » Cod sursa (job #3039278) | Cod sursa (job #1027343) | Cod sursa (job #1209083) | Cod sursa (job #2908871) | Cod sursa (job #2857123)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 32000;
const int lg = 15;
vector<vector<pair<int,int>>> dx(nmax+5);
int up[nmax+5][lg+5], rmq[nmax+5][lg+5];
int niv[nmax+5];
bool viz[nmax+5];
void dfs(int node) {
viz[node] = true;
for(int i=1; i<=lg; i++)
up[node][i] = up[up[node][i-1]][i-1];
for(int i=1; i<=lg; i++)
rmq[node][i] = min(rmq[node][i-1], rmq[up[node][i-1]][i-1]);
for(auto i : dx[node]) {
if(!viz[i.first]) {
niv[i.first] = niv[node] + 1;
up[i.first][0] = node;
rmq[i.first][0] = i.second;
dfs(i.first);
}
}
}
int query(int a, int b) {
if(niv[a]<niv[b]) swap(a,b);
int ans = 1e9;
for(int i=lg; i>=0; i--)
if(niv[up[a][i]]>=niv[b]) {
ans = min(ans, rmq[a][i]);
a = up[a][i];
}
if(a==b) return ans;
for(int i=lg; i>=0; i--) {
if(up[a][i]!=up[b][i]) {
ans = min(ans, rmq[a][i]);
ans = min(ans, rmq[b][i]);
a = up[a][i];
b = up[b][i];
}
}
ans = min(ans, rmq[a][0]);
ans = min(ans, rmq[b][0]);
return ans;
}
int main () {
ifstream f ("atac.in");
ofstream g ("atac.out");
int n,m,p; f >> n >> m >> p;
for(int i=2; i<=n; i++) {
int x,cost; f >> x >> cost;
dx[i].emplace_back(x,cost);
dx[x].emplace_back(i,cost);
}
niv[1] = 1; dfs(1);
int x,y,a,b,c,d; f >> x >> y >> a >> b >> c >> d;
int ans[m+5];
for(int i=1; i<=m; i++) {
int z;
if(x==y) z = 0;
else z = query(x,y);
x = (x*a + y*b) % n + 1;
y = (y*c + z*d) % n + 1;
ans[i] = z;
}
for(int i=m-p+1; i<=m; i++) g << ans[i] << "\n";
return 0;
}