Pagini recente » Cod sursa (job #1510427) | Cod sursa (job #764182) | Cod sursa (job #622674) | Cod sursa (job #1135795) | Cod sursa (job #1709251)
#include <fstream>
#include <vector>
#include <set>
#define NMAX 32005
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int r[NMAX][25] , t[NMAX][25] , log[NMAX] , tata[NMAX] , cost[NMAX] , nivel[NMAX];
int n , m , x , y , sol , a , b , c , d , p;
vector <vector <pair <int , int> > > v;
void dfs(int node , int tt);
int solve(int x , int y);
int main() {
f >> n >> m >> p;
v.resize(n + 2);
for(int i = 2 ; i <= n ; ++i) {
f >> y >> c;
x = i;
v[x].push_back(make_pair(y , c));
v[y].push_back(make_pair(x , c));
}
nivel[1] = 1;
dfs(1 , -1);
for(int i = 1 ; i <= n ; ++i) {
t[i][0] = tata[i];
r[i][0] = cost[i];
for(int j = 1 ; (1 << j) <= nivel[i] ; ++j) {
t[i][j] = t[t[i][j - 1]][j - 1];
r[i][j] = min(r[i][j - 1] , r[t[i][j - 1]][j - 1]);
}
}
for(int i = 1 ; i <= n ; ++i) {
int aux = 1;
while((1 << aux) <= i) {
++aux;
}
log[i] = aux - 1;
}
f >> x >> y >> a >> b >> c >> d;
for(int i = 1 ; i <= m; ++i) {
int z = solve(x , y);
int xx = (x * a + y * b) % n + 1;
int yy = (y * c + z * d) % n + 1;
x = xx;
y = yy;
if(i > m - p)
g << z << '\n';
}
return 0;
}
int solve(int x , int y) {
int mn = 500000;
if(nivel[x] < nivel[y]) {
swap(x , y);
}
int dif = nivel[x] - nivel[y];
int j = 0;
while(dif) {
if(dif % 2 != 0) {
mn = min(mn , r[x][j]);
x = t[x][j];
}
++j;
dif /= 2;
}
if(x == y) {
return x;
}
int pas = log[nivel[x]];
while(pas) {
if(t[x][pas] != t[y][pas]) {
mn = min(mn , r[x][pas]);
mn = min(mn , r[y][pas]);
x = t[x][pas];
y = t[y][pas];
}
--pas;
}
if(t[x][pas] != t[y][pas]) {
mn = min(mn , r[x][pas]);
mn = min(mn , r[y][pas]);
x = t[x][pas];
y = t[y][pas];
}
mn = min(mn , r[x][0]);
mn = min(mn , r[y][0]);
return mn;
}
void dfs(int node , int tt) {
if(node != 1) {
nivel[node] = 1 + nivel[tt];
}
for(int it = 0 ; it < v[node].size() ; ++it) {
if(v[node][it].first != tt) {
cost[v[node][it].first] = v[node][it].second;
tata[v[node][it].first] = node;
dfs(v[node][it].first , node);
}
}
}