Cod sursa(job #1930057)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 18 martie 2017 14:53:10
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int n,q,t,a,b,x,y,poz,nr,i,j,k,c,d,A,B,z,m,p,L[1<<15],P[1<<15],put[1<<17],rmq[17][1<<18],V[17][1<<18],T[17][1<<18];
bool viz[1<<15];
vector <pair <int,int> > G[1<<15];
void dfs(int x,int level)
{
    for(int i=1;i<=15;++i)
    {
        T[i][x]=T[i-1][T[i-1][k]];
        V[i][x]=min(V[i-1][x],V[i-1][T[i-1][x]]);
    }
    viz[x]=1;
    L[x]=level;
    rmq[0][++nr]=x;
    P[x]=nr;
    for(int i=0;i<(int)G[x].size();++i)
        if(!viz[G[x][i].first])
    {
        V[0][G[x][i].first]=G[x][i].second;
        T[0][G[x][i].first]=x;
        dfs(G[x][i].first,level+1);
        rmq[0][++nr]=x;
    }
}
void build_rmq()
{
    put[1]=0;
    for(i=2;i<=nr;i++) put[i]=put[i/2]+1;
    for(i=1;(1<<i)<=nr;++i)
        for(j=1,k=1<<(i-1);j<=nr;++j)
            rmq[i][j]=(L[rmq[i-1][j]]<L[rmq[i-1][j+k]]?rmq[i-1][j]:rmq[i-1][j+k]);
}
int LCA(int x,int y)
{
    if(P[x]>P[y]) swap(x,y);
    int d=put[P[y]-P[x]];
    int nod=rmq[d][P[y]-(1<<d)+1];
    if(L[nod]>L[rmq[d][P[x]]]) nod=rmq[d][P[x]];
    return nod;
}
int query(int x,int y)
{
    if(x==y) return 1<<30;
    int dist=L[y]-L[x],sol=1<<30;
    for(int i=14;i>=0&&y>1;--i)
        if(dist&(1<<i))
        {
            sol=min(sol,V[i][y]);
            y=T[i][y];
            dist-=(1<<i);
        }
    return sol;
}
int main()
{
    f>>n>>m>>p;
    for(i=2;i<=n;++i)
    {
        f>>x>>y;
        G[x].push_back(make_pair(i,y));
        G[i].push_back(make_pair(x,y));
    }
    dfs(1,1);
    build_rmq();
    f>>x>>y>>a>>b>>c>>d;
    for(i=1;i<=m;++i)
    {
        if(x!=y)
        {
            int rad=LCA(x,y);
            z=min(query(rad,x),query(rad,y));
        }
        else z=0;
        if(i>=m-p+1) g<<z<<'\n';
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    return 0;
}