Cod sursa(job #2446015)

Utilizator CharacterMeCharacter Me CharacterMe Data 6 august 2019 18:28:38
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <bits/stdc++.h>
#define maxl int(log2(32001)+2)
#define max2l int(log2(64001)+2)
#define inf 2147483647
using namespace std;
int n, m, p, i, j, k, x, y, a, b, c, d, z, v;
int sol[maxl][32001], level[32001], dad[32001], up[32001], nodes[maxl][32001], rmq[max2l][64001], first[32001];
vector<int> graph[32001];

void read();
void prep();
void write();
void dfs(int node);
void lca(int node);
int mn(int node1, int node2);
void change(int &x, int &y, int z);
int main()
{
    read();
    prep();
    write();
    return 0;
}
void read(){
    freopen("atac.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &p);
    up[1]=inf; level[0]=-1;
    for(i=2; i<=n; ++i){
        int head, cost;
        scanf("%d%d", &head, &cost);
        graph[head].push_back(i);
        dad[i]=head;
        up[i]=cost;
    }
    scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    return;
}
void prep(){
    dfs(1);
    lca(1);
    for(j=1; (1<<j)<=v; ++j){
        for(i=1; i<=v; ++i){
            int next=i+(1<<(j-1));
            rmq[j][i]=rmq[j-1][i];
            if(next<=v) rmq[j][i]=mn(rmq[j][i], rmq[j-1][next]);
        }
    }
    return;
}
void write(){
    freopen("atac.out", "w", stdout);
    while(m--){
        if(x!=y){
            bool rev=false;
            int fy=first[y], fx=first[x];
            if(fy<fx) {swap(x, y); swap(fx, fy); rev=true;}
            int j=int(log2(fy-fx+1));
            int str=mn(rmq[j][fx], rmq[j][fy-(1<<j)+1]);
            int p1=level[x]-level[str], p2=level[y]-level[str];
            z=inf;
            int node1=x, node2=y;
            while(p1){
                j=int(log2(p1));
                z=min(z, sol[j][node1]);
                node1=nodes[j][node1];
                p1-=(1<<j);
            }
            while(p2){
                j=int(log2(p2));
                z=min(z, sol[j][node2]);
                node2=nodes[j][node2];
                p2-=(1<<j);
            }
            if(m+1<=p) printf("%d\n", z);
            if(rev==true) swap(x, y);
            change(x, y, z);
        }
        else{
            z=0;
            if(m+1<=p) printf("%d\n", z);
            change(x, y, z);
        }
    }
}
void dfs(int node){
    level[node]=level[dad[node]]+1;
    sol[0][node]=up[node]; nodes[0][node]=dad[node];
    int next=dad[node];
    for(j=1; (1<<j)<=level[node]; ++j){
        sol[j][node]=min(sol[j-1][node], sol[j-1][next]);
        nodes[j][node]=nodes[j-1][next];
        next=nodes[j-1][next];
    }
    for(auto i:graph[node]){
        dad[i]=node;
        dfs(i);
    }
    return;
}
void lca(int node){
    for(auto i:graph[node]){
        rmq[0][++v]=node; if(!first[node]) first[node]=v;
        lca(i);
    }
    rmq[0][++v]=node; if(!first[node]) first[node]=v;
    return;
}
int mn(int node1, int node2){
    if(level[node1]<=level[node2]) return node1;
    return node2;
}
void change(int &x, int &y, int z){
    x=(a*x+b*y)%n+1;
    y=(c*y+d*z)%n+1;
    return;
}