Pagini recente » Cod sursa (job #1996380) | Cod sursa (job #1355513) | Cod sursa (job #1243723) | Cod sursa (job #312161) | Cod sursa (job #2456180)
#include <bits/stdc++.h>
using namespace std;
ifstream si("atac.in");
ofstream so("atac.out");
const int NMax = 32050;
const int LMax = 20;
int lvl[NMax];
pair<int, int> lift[LMax][NMax];
vector<vector<pair<int, int>>> g;
void dfs(int node, int father, int cost) {
for(auto x: g[node]) {
if(x.first==father)
continue;
lvl[x.first]=lvl[node]+1;
dfs(x.first, node, x.second);
}
lift[0][node]={father, cost};
}
int lca(int x, int y) {
if(x==y)
return 0;
if(lvl[x]<lvl[y]) {
swap(x, y);
}
int logx, logy;
for(logx=1; (1<<logx)<lvl[x]; ++logx);
for(logy=1; (1<<logy)<lvl[y]; ++logy);
int mn=INT_MAX;
for(int i=logx; i>=0; --i) {
if(lvl[x]-(1<<i)>=lvl[y]) {
mn=min(mn, lift[i][x].second);
x=lift[i][x].first;
}
}
if(x==y)
return mn;
for(int i=logy; i>=0; --i) {
if(lift[i][x].first!=0&&lift[i][x].first!=lift[i][y].first) {
mn=min({mn, lift[i][x].second, lift[i][y].second});
x=lift[i][x].first;
y=lift[i][y].first;
}
}
return min({mn, lift[0][x].second, lift[0][y].second});
}
int main()
{
int n, m, p;
si>>n>>m>>p;
g.assign(n+5, {});
for(int i=2; i<=n; ++i) {
int u, v;
si>>u>>v;
g[u].push_back({i, v});
g[i].push_back({u, v});
}
dfs(1, 0, INT_MAX);
lift[0][0].second=INT_MAX;
for(int i=1; i<LMax; ++i) {
for(int j=0; j<=n; ++j) {
pair<int, int> next=lift[i-1][lift[i-1][j].first];
lift[i][j]={next.first, min(lift[i-1][j].second, next.second)};
}
}
long long x, y, a, b, c, d;
si>>x>>y>>a>>b>>c>>d;
for(int i=1; i<=m; ++i) {
long long z=lca(x, y);
if(i>=m-p+1) {
so<<z<<'\n';
}
int nx=(a*x+b*y)%n+1;
int ny=(c*y+d*z)%n+1;
//cout<<nx<<' '<<ny<<' '<<z<<'\n';
x=nx;
y=ny;
}
return 0;
}