Cod sursa(job #2445540)

Utilizator CharacterMeCharacter Me CharacterMe Data 4 august 2019 15:53:30
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.06 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstdlib>
#define pii pair<int, int>
#define mp make_pair
#define f(x) (x&(-x))
#define inf 100001
using namespace std;
///variables
int n, m, p, i, j, k, a, b, c, d, x, y, z, v;
int weigth[32001], head[32001], group[32001], up[32001], posg[32001], height[32001];
vector<pii> graph[32001];
vector<int> hpd[32001];
struct AIB{
    int *v;
    int sz;
    void change(int pos, int val, int left, int right, int position);
    int query(int pos1, int pos2, int left, int right, int position);
    void start();
} aibs[32001];
///functions
void read();
void prepare();
void dfs(int node);
void create_hp(int node);
int mn(int node1, int node2);
void write();
void cont(int &x, int &y, int z);
int sol(int x, int y);
int main()
{
    read();
    prepare();
    write();
    return 0;
}
void read(){
    freopen("atac.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &p);
    for(i=2; i<=n; ++i){
        int node, cost;
        scanf("%d%d", &node, &cost);
        graph[node].push_back(mp(i, cost));
        up[i]=cost;
    }
    scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    return;
}
void prepare(){
    height[1]=0; height[0]=-1;
    dfs(1); ++v; hpd[v].push_back(0);
    create_hp(1);
    up[1]=up[0]=inf;
    for(i=1; i<=v; ++i) {
        aibs[i].v=(int *)realloc(aibs[i].v, 4*sizeof(int)*(hpd[i][0]+1));
        aibs[i].sz=hpd[i][0];
        aibs[i].start();
        for(int j=1; j<=hpd[i][0]; ++j) aibs[i].v[j]=0;
        for(int j=1; j<=hpd[i][0]; ++j) aibs[i].change(j, hpd[i][j], 1, aibs[i].sz, 1);
    }
    return;
}
void write(){
    freopen("atac.out", "w", stdout);
    while(m--){
        if(x==y) z=0;
        else z=sol(x, y);
        if(m+1<=p) printf("%d\n", z);
        cont(x, y, z);
    }
}
void dfs(int node){
    ++weigth[node];
    for(auto i:graph[node]) {
        height[i.first]=height[node]+1;
        dfs(i.first);
        weigth[node]+=weigth[i.first];
    }
    return;
}
void create_hp(int node){
    hpd[v].push_back(node);
    ++hpd[v][0]; group[node]=v; posg[node]=hpd[v][0];
    int next=0, mx=-1;
    for(auto i:graph[node]){
        if(weigth[i.first]>mx){
            mx=weigth[i.first]; head[i.first]=head[node];
            next=i.first;
        }
    }
    if(next)create_hp(next);
    for(auto i:graph[node]) if(i.first!=next){
        ++v; hpd[v].push_back(0); head[i.first]=node;
        create_hp(i.first);
    }
}
void AIB::change(int pos, int val, int left, int right, int position){
    if(left==right) {v[position]=val; return;}
    int mid=(left+right)/2;
    if(pos<=mid) change(pos, val, left, mid, 2*position);
    else change(pos, val, mid+1, right, 2*position+1);
    v[position]=mn(v[2*position], v[2*position+1]);
    return;
}
int AIB::query(int pos1, int pos2, int left, int right, int position){
    if(pos1==left && pos2==right) return v[position];
    int mid=(left+right)/2;
    if(pos2<=mid) return query(pos1, pos2, left, mid, 2*position);
    else if(pos1>mid) return query(pos1, pos2, mid+1, right, 2*position+1);
    else return mn(query(pos1, mid, left, mid, 2*position), query(mid+1, pos2, mid+1, right, 2*position+1));
}
void AIB::start(){
    for(int j=1; j<=4*sz; ++j) v[j]=0;
    return;
}
int mn(int node1, int node2){
    if(up[node1]<=up[node2]) return node1;
    return node2;
}
int sol(int x, int y){
    int z=inf;
    if(x>y) swap(x, y);
    while(true){
        int hx=head[x], hy=head[y];
        if(group[x]==group[y]){
            if(x==y) return z;
            if(height[x]>height[y]) swap(x, y);
            x=hpd[group[x]][posg[x]+1];
            z=min(z, up[aibs[group[x]].query(posg[x], posg[y], 1, aibs[group[x]].sz, 1)]);
            break;
        }
        if(height[hx]>height[hy]){swap(hx, hy); swap(x, y);}
        if(posg[y]>1)z=min(z, up[aibs[group[y]].query(2, posg[y], 1, aibs[group[y]].sz, 1)]);
        z=min(z, up[hpd[group[y]][1]]);
        y=hy;
    }
    return z;
}
void cont(int &x, int &y, int z){
    x=(a*x+b*y)%n+1;
    y=(c*y+d*z)%n+1;
}