Cod sursa(job #2258756)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 11 octombrie 2018 22:36:46
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#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;
}