Cod sursa(job #2632197)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 2 iulie 2020 15:09:01
Problema Atac Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.5 kb
#include <bits/stdc++.h>
#define DIM 35000
#define DIMM 500010
#define INF 2000000000
using namespace std;
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};


int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],Size[DIM],level[DIM];
int E[DIM*4],p[DIM*4],first[DIM],val[DIM],ans[DIMM];
int nr_chains,n,m,P,i,j,x,y,sol,k,cost,a,b,c,d;
pair <int,int> rmq[20][DIM*4];
vector <int> chains[DIM],aint[DIM];
vector <pair<int,int> > L[DIM];


void dfs (int nod, int tata){

    level[nod] = 1 + level[tata];
    Size[nod] = 1;
    E[++k] = nod;
    first[nod] = k;
    int ok = 0;
    for (auto it : L[nod]){
        int vecin = it.first, cost = it.second;
        if (vecin != tata){
            val[vecin] = cost;
            ok = 1;
            dfs (vecin,nod);
            Size[nod] += Size[vecin];
            E[++k] = nod;
        }
    }

    if (!ok){
        nr_chains++;
        chains[nr_chains].push_back(0);
        chains[nr_chains].push_back(nod);
        whatChain[nod] = nr_chains;
        positionInChain[nod] = 1;
    } else {
        int maxi = 0, heavy_son = 0;
        for (auto it : L[nod]){
            int vecin = it.first;
            if (vecin != tata && Size[vecin] > maxi)
                maxi = Size[vecin], heavy_son = vecin;
        }

        chains[whatChain[heavy_son]].push_back(nod);
        positionInChain[nod] = chains[whatChain[heavy_son]].size()-1;
        whatChain[nod] = whatChain[heavy_son];

        for (auto it : L[nod]){
            int vecin = it.first;
            if (vecin != tata && vecin != heavy_son)
                chainFatherNode[whatChain[vecin]] = nod;
        }}}

void build (int chain, int nod, int st, int dr){
    if (st == dr){
        aint[chain][nod] = val[chains[chain][st]];
        return;
    }
    int mid = (st + dr)>>1;
    build (chain,nod<<1,st,mid);
    build (chain,(nod<<1)|1,mid+1,dr);
    aint[chain][nod] = min (aint[chain][nod<<1],aint[chain][(nod<<1)|1]);
}

void query_aint (int chain, int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol = min (sol,aint[chain][nod]);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query_aint (chain,nod<<1,st,mid,x,y);
    if (y > mid)
        query_aint (chain,(nod<<1)|1,mid+1,dr,x,y);
}

int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy - posx + 1];
    pair <int, int> sol = min (rmq[nr][posx], rmq[nr][posy - (1<<nr) + 1]);
    return E[sol.second];
}

void query (int x, int y, int lca){
    if (whatChain[x] == whatChain[y]){

        int posx = positionInChain[x], posy = positionInChain[y];
        if (posx > posy)
            swap  (posx,posy), swap (x,y);
        if (x == lca)
            posx++;
        if (y == lca)
            posy--;

        if (posx <= posy)
            query_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy);

        return;
    }

    if (level[chainFatherNode[whatChain[x]]] <= level[chainFatherNode[whatChain[y]]])
        swap (x,y);

    int posx = positionInChain[x], posy = chains[whatChain[x]].size()-1;
    if (x == lca)
        posx++;
    if (chains[whatChain[x]][posy] == lca)
        posy--;
    if (posx <= posy)
        query_aint (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy);

    int nr = chainFatherNode[whatChain[x]];
    query (nr,y,lca);
}

int main (){

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

    fin>>n>>m>>P;
    for (i=2;i<=n;i++){
        fin>>x>>cost;
        L[i].push_back(make_pair(x,cost));
        L[x].push_back(make_pair(i,cost));
    }

    dfs (1,0);

    for (i=1;i<=nr_chains;i++){
        for (j=1;j<=4*chains[i].size();j++)
            aint[i].push_back(0);
        build (i,1,1,chains[i].size()-1);
    }

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;

    fin>>x>>y>>a>>b>>c>>d;
    sol = INF;
    query (x,y,get_lca(x,y));
    if (x == y)
        sol = 0;
    ans[1] = sol;

    for (i=2;i<=m;i++){
        x = (x * a + y * b) % n + 1;
        y = (y * c + sol * d) % n + 1;
        sol = INF;
        query (x,y,get_lca(x,y));
        if (x == y)
            sol = 0;
        ans[i] = sol;
    }

    for (i=m-P+1;i<=m;i++)
        fout<<ans[i]<<"\n";

    return 0;
}