Cod sursa(job #1073264)

Utilizator stefanzzzStefan Popa stefanzzz Data 5 ianuarie 2014 21:14:26
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#define MAXN 32005
#define MAXLOGN 17
#define INF 1000000
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");

int n,m,p,x,y,a,b,c,d,sol,cst,tata[MAXN][MAXLOGN],mn[MAXN][MAXLOGN],lvl[MAXN],xx,yy;
vector< pair<int,int> > G[MAXN];

void DFS(int nod);
inline int MIN(int x1,int x2){
    return (x1<x2)?x1:x2;}

int main()
{
    int i,j;
    f>>n>>m>>p;
    for(i=2;i<=n;i++){
        f>>x>>cst;
        G[i].push_back(make_pair(x,cst));
        G[x].push_back(make_pair(i,cst));}
    f>>x>>y>>a>>b>>c>>d;
    tata[1][0]=-1;
    DFS(1);
    for(i=1;i<=m;i++){
        xx=x;yy=y;
        sol=INF;
        if(lvl[yy]>lvl[xx])
            swap(xx,yy);
        for(j=MAXLOGN-1;j>=0;j--)
            if(lvl[xx]-(1<<j)>=lvl[yy]){
                if(mn[xx][j]<sol)
                    sol=mn[xx][j];
                xx=tata[xx][j];}
        if(xx==yy){
            if(sol==INF)
                sol=0;
            if(i+p>m)
                g<<sol<<'\n';
            x=(x*a+y*b)%n+1;
            y=(y*c+sol*d)%n+1;
            continue;}
        for(j=MAXLOGN-1;j>=0;j--)
            if(tata[xx][j]!=tata[yy][j]){
                if(mn[xx][j]<sol)
                    sol=mn[xx][j];
                if(mn[yy][j]<sol)
                    sol=mn[yy][j];
                xx=tata[xx][j];
                yy=tata[yy][j];}
        if(mn[xx][0]<sol)
            sol=mn[xx][0];
        if(mn[yy][0]<sol)
            sol=mn[yy][0];
        if(i+p>m)
            g<<sol<<'\n';
        x=(x*a+y*b)%n+1;
        y=(y*c+sol*d)%n+1;}
    f.close();
    g.close();
    return 0;
}

void DFS(int nod){
    int i,j;
    for(i=0;i<G[nod].size();i++){
        xx=G[nod][i].first;
        if(!tata[xx][0]){
            lvl[xx]=lvl[nod]+1;
            tata[xx][0]=nod;
            mn[xx][0]=G[nod][i].second;
            yy=nod;
            for(j=1;tata[yy][j-1]>0;j++){
                tata[xx][j]=tata[yy][j-1];
                mn[xx][j]=MIN(mn[xx][j-1],mn[yy][j-1]);
                yy=tata[xx][j];}
            DFS(xx);}}}