Cod sursa(job #1936530)

Utilizator GinguIonutGinguIonut GinguIonut Data 23 martie 2017 10:30:56
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <vector>

#define nMax 32001
#define log2Max 16
#define INF 100000000
#define pb push_back
#define mkp make_pair
#define x first
#define y second

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

int n, t, p, X, Y, A, B, C, D, Z;
int lev[nMax], TT[log2Max][nMax], dist[log2Max][nMax];
vector<pair<int, int> > G[nMax];

void dfs(int node)
{
    for(vector<pair<int, int> >::iterator it=G[node].begin(); it!=G[node].end(); it++)
    {
        int fiu=it->first, cost=it->second;
        if(fiu==TT[0][node])
            continue;
        lev[fiu]=lev[node]+1;
        TT[0][fiu]=node, dist[0][fiu]=cost;
        dfs(fiu);
    }
}

int solve(int a, int b)
{
    if(lev[a]>lev[b])
        swap(a, b);
    int Sol=INF;
    for(int len=15, diff=lev[b]-lev[a]; len>=0 && diff; len--)
    {
        if((1 << len)<=diff)
        {
            diff-=(1 << len);
            Sol=min(Sol, dist[len][b]);
            b=TT[len][b];
        }
    }
    for(int len=15; len>=0 && a!=b; len--)
    {
        if(TT[len][a]!=TT[len][b])
        {
            Sol=min(Sol, min(dist[len][a], dist[len][b]));
            a=TT[len][a], b=TT[len][b];
        }
    }
    if(a!=b)
        Sol=min(Sol, min(dist[0][a], dist[0][b]));
    if(Sol==INF)
        Sol=0;
    return Sol;
}

int main()
{
    int a, b;
    fin>>n>>t>>p;
    for(int i=2; i<=n; i++)
    {
        fin>>a>>b;
        G[a].pb(mkp(i, b));
        G[i].pb(mkp(a, b));
    }
    lev[1]=1;
    dfs(1);

    for(int len=0; len<=15; len++)
        dist[len][0]=INF;
    for(int len=1; (1 << len)<=n; len++)
    {
        for(int i=1; i<=n; i++)
        {
            TT[len][i]=TT[len-1][TT[len-1][i]];
            dist[len][i]=min(dist[len-1][i], dist[len-1][TT[len-1][i]]);
        }
    }

    fin>>X>>Y>>A>>B>>C>>D;
    for(int i=1; i<=t; i++)
    {
        int Z=solve(X, Y);
        if(i>=t-p+1)
            fout<<Z<<'\n';
        X=(X*A + Y*B)%n+1;
        Y=(Y*C + Z*D)%n+1;
    }
}