Pagini recente » Rating Muntean Tiberiu (tiberiumuntean) | Cod sursa (job #2904640) | Cod sursa (job #1034931) | Cod sursa (job #2059941) | Cod sursa (job #2188566)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
int const nmax = 32000;
int const inf = 1000000000;
#define MIN(a , b) ((a < b) ? a : b)
struct Edge{
int to;
int cost;
};
vector < Edge > g[5 + nmax];
int level[5 + nmax];//nivelul nodului
int euler[5 + 4 * nmax] , ep = 0;//parcurgere euler
int poseuler[5 + 4 * nmax]; // pozitia nodului in parcurgere
Edge path[20][5 + nmax];
int n;
void build(int node , int levelp , int parent){
level[node] = levelp;
for(int h = 0 ; h < g[node].size() ; h++){
if(g[node][h].to != parent){
build(g[node][h].to , levelp + 1 , node);
path[0][g[node][h].to] = {node , g[node][h].cost };
}
}
}
void computepaths(){
path[0][1] = {0 , inf};
for(int h = 1 ; h < 20 ;h++)
for(int i = 0 ; i <= n ;i++)
path[h][i] = {0 , inf};
path[0][0] = {0 , inf};
for(int h = 1 ; h < 20 ;h++){
for(int i = 1 ; i <= n ;i++){
int jump = path[h - 1][i].to;
int cost = MIN(path[h - 1][i].cost , path[h - 1][jump].cost);
path[h][i] = {path[h - 1][jump].to , cost};
}
}
}
void geteuler(int node , int parent){
for(int h = 0 ;h < g[node].size() ;h++){
if(g[node][h].to != parent){
geteuler(g[node][h].to ,node);
euler[++ep] = node;
poseuler[node] = ep;
}
}
if(g[node].size() == 1){
euler[++ep] = node;
poseuler[node] = ep;
}
}
int lg[5 + 4 * nmax];
int rmq[20][5 + 4 * nmax];
void buildrmq(){
lg[0] = lg[1] = 0;
for(int i = 2 ; i <= ep ;i++)
lg[i] = lg[i / 2] + 1;
for(int i = 1 ; i <= ep ;i++)
rmq[0][i] = euler[i];
for(int h = 1 ; h < 20 ;h++){
int jump = (1 << (h - 1));
for(int i = 1 ; i <= ep - (1 << h) + 1 ;i++){
int a = rmq[h - 1][i];
int b = rmq[h - 1][i + jump];
if(level[a] < level[b]){
rmq[h][i] = a;
} else
rmq[h][i] = b;
}
}
}
int getlca(int a , int b){
int x = poseuler[a] , y = poseuler[b];
if(y < x)
swap(x , y);
int dist = lg[y - x];
int result1 = rmq[dist][x];
int result2 = rmq[dist][y - (1 << dist) + 1];
if(level[result1] < level[result2])
return result1;
else
return result2;
}
int getcost(int node , int levels){
int cost = inf;
for(int h = 19 ; 0 <= h ;h--){
if(0 < ((1 << h) & levels)){
cost = MIN(cost , path[h][node].cost);
node = path[h][node].to;
}
}
return cost;
}
int solve(int a , int b){
cout << a << " " << b << '\n';
int lca = getlca(a , b);
//cout << level[a] << " " << level[b] << " " <<level[lca] << '\n';
cout << MIN(getcost(a , level[a] - level[lca]) , getcost(b , level[b] - level[lca] )) << '\n' << '\n';
return MIN(getcost(a , level[a] - level[lca]) , getcost(b , level[b] - level[lca]));
}
void debug(){
/*
cout << "Level :\n";
for(int i = 1 ; i <= n ;i++)
cout << level[i] << " " ;
cout << '\n';
//*/
/*
cout << "Euler : \n";
for(int i = 1 ; i <= ep ;i++)
cout << euler[i] << " ";
cout << '\n';
//*/
/*
cout << "Lca : \n";
for(int i = 1 ; i <= n ;i++)
for(int j = i ; j <= n ;j++)
cout << i << " " << j <<" "<<getlca(i , j) << '\n';
//*/
/*
cout << "Paths :\n";
for(int h = 0 ; h < 6 ;h++){
for(int i = 1 ; i <= n ;i++)
cout << h << " " << i <<" "<<path[h][i].cost <<" " <<path[h][i].to << '\n';
cout << '\n';
}
*/
/*
cout<< "Costs :\n";
for(int h = 1 ; h <= 3 ;h++){
for(int i = 1 ; i <= n ;i++)
cout << h << " " << i << " " << getcost(i , h) << '\n';
}
//*/
}
int main()
{
int m , p;
in >> n >> m >> p;
for(int i = 2 ; i <= n ;i++){
int a , b;
in >> a >> b;
g[i].push_back({a , b});
g[a].push_back({i , b});
}
build(1 , 1 , 0);
geteuler(1 , 0);
buildrmq();
computepaths();
debug();
int x , y , a , b , c , d;
in >> x >> y >> a >> b >> c >> d;
int result = 0;
for(int i = 1 ; i <= m ;i++){
if(i == 1)
result = solve(x , y);
else{
int x2 = (x * a + y * b) % n + 1;
int y2 = (y * c + result * d) % n + 1;
result = solve(x2 , y2);
x = x2;
y = y2;
}
if(m - p + 1 <= i)
out << result << '\n';
}
return 0;
}