Cod sursa(job #1929943)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 18 martie 2017 12:43:52
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 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,v[1<<15],st[1<<15],dr[1<<15],L[1<<15],P[1<<15],put[1<<17],rmq[17][1<<18],AI[1<<19];
bool viz[1<<15];
vector <pair <int,int> > G[1<<15];
void dfs(int x,int level)
{
    viz[x]=1;
    st[x]=++poz;
    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])
    {
        dfs(G[x][i].first,level+1);
        v[st[G[x][i].first]]=G[x][i].second;
        rmq[0][++nr]=x;
    }
    dr[x]=++poz;
}
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;
}
void build(int nod,int left,int right)
{
    if(left==right)
    {
        AI[nod]=v[left];
        return;
    }
    int mij=(left+right)/2;
    build(2*nod,left,mij);
    build(2*nod+1,mij+1,right);
    AI[nod]=min(AI[2*nod],AI[2*nod+1]);
}
void query(int nod,int left,int right)
{
    if(A<=left&&right<=B)
    {
        z=min(AI[nod],z);
        return;
    }
    int mij=(left+right)/2;
    if(A<=mij) query(2*nod,left,mij);
    if(B>mij) query(2*nod+1,mij+1,right);
}
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));
    }
    for(i=1;i<=100*n;++i) v[i]=AI[i]=1<<30;
    dfs(1,1);
    build_rmq();
    build(1,1,poz);
    f>>x>>y>>a>>b>>c>>d;
    for(i=1;i<=m;++i)
    {
        if(x!=y)
        {
            int rad=LCA(x,y);
            //g<<x<<' '<<y<<' '<<rad<<'\n';
            z=1<<30;
            A=st[rad]+1;
            B=st[x];
            //g<<A<<' '<<B<<'\n';
            if(A<=B) query(1,1,poz);
            B=st[y];
            if(A<=B) query(1,1,poz);
        }
        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;
}