Cod sursa(job #2131228)

Utilizator patcasrarespatcas rares danut patcasrares Data 14 februarie 2018 15:58:03
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<algorithm>
#include<iostream>
#include<vector>
#define DN 32005
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
int n,m,p,z,u,c,pr1[15][DN],pr2[15][DN],niv[DN],lg[DN];
int f,g,a,b,d;
vector<pair<int,int> >v[DN];
void dfs(int nod)
{
    for(auto i:v[nod])
        if(niv[i.x]==0)
        {
            pr1[0][i.x]=nod;
            pr2[0][i.x]=i.y;
            niv[i.x]=niv[nod]+1;
            dfs(i.x);
        }
}
void lca(int a,int b)
{
    int d,dr;
    if(niv[a]<niv[b])
        swap(a,b);
    d=niv[a]-niv[b];
    dr=lg[d];
    for(int i=dr;i>=0&&d;i--)
        if((1<<i)<=d)
        {
            d-=(1<<i);
            z=min(z,pr2[i][a]);
            a=pr1[i][a];
        }
    if(a==b)
        return;
    dr=lg[niv[a]];
    for(int i=dr;i>=0;i--)
        if(pr1[i][a]!=pr1[i][b])
        {
            z=min(z,pr2[i][a]);
            z=min(z,pr2[i][b]);
            a=pr1[i][a];
            b=pr1[i][b];
        }
    z=min(z,pr2[0][a]);
    z=min(z,pr2[0][b]);
}
int main()
{
    fin>>n>>m>>p;
    for(int i=1;i<=n;i++)
        for(int j=0;(1<<j)<=i;j++)
            lg[i]=j;
    for(int i=2;i<=n;i++)
    {
        fin>>u>>c;
        v[u].pb({i,c});
        v[i].pb({u,c});
    }
    niv[1]=1;
    dfs(1);
    pr2[0][1]=1e9;
    for(int j=1;j<15;j++)
        for(int i=1;i<=n;i++)
        {
            pr1[j][i]=pr1[j-1][pr1[j-1][i]];
            pr2[j][i]=min(pr2[j-1][i],pr2[j-1][pr1[j-1][i]]);
        }
    fin>>f>>g>>a>>b>>c>>d;
    for(int i=1;i<=m;i++)
    {
        z=1e9;
        lca(f,g);
        if(z==1e9)
            z=0;
        if(m-i+1<=p)
            fout<<z<<'\n';
        f=(1LL*f*a+1LL*g*b)%n+1;
        g=(1LL*g*c+1LL*z*d)%n+1;
    }
}