Cod sursa(job #2092268)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 21 decembrie 2017 14:48:40
Problema Atac Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
int rmq[26][64010],pt[26];
int level[32005],poz[32005],ap[32005],euler[64010];
pair<int,int>stramosi[26][32005];
bool hz[32005];
vector<pair<int,int> >v[32005];
int k,n,m,p,a,b,c,d,x,y,z,z1,z2,A,B,C,D,dx,ad,num,s1,s2,aux;
void dfs (int nod) {
    int vecin;
    rmq[0][++k] = nod;
    poz[nod] = k;
    hz[nod] = 1;
    for (int i = 0; i < v[nod].size(); i ++) {
        vecin = v[nod][i].first;
        if (hz[vecin] == 0) {
            level[vecin] = level[nod] + 1;
            dfs (vecin);
            rmq[0][++k] = nod;
        }
    }

}
int LCA (int x, int y) {
    int a = max( poz[x] , poz[y]) - min (poz[x], poz[y]) + 1;
    a = ap[a];
    int b = min(poz[x], poz[y]);
    int c = max (poz[x], poz[y]) - pt[a] + 1;

    if (level[rmq[a][b]] < level[rmq[a][c]]) {
        return rmq[a][b];
    }
    else {
        return rmq[a][c];
    }
}
void dfs_dinamica (int nod) {
    hz[nod] = true;
    int vecin,cost;
    for (int i = 0; i < v[nod].size(); i ++) {
        vecin = v[nod][i].first;
        cost = v[nod][i].second;
        if (hz[vecin] == false) {
            stramosi[0][vecin].first = nod;
            stramosi[0][vecin].second = cost;
            dfs_dinamica (vecin);
        }
    }
}
int main (void) {
    in >> n >> m >> p;
    for (int i = 2; i <= n; i ++ ) {
        in >> b >> c;
        v[i].push_back (make_pair(b,c));
        v[b].push_back (make_pair(i,c));
    }
    level[1] = 1;
    dfs (1);
    pt[0] = 1;
    for (int i = 1; i <= 25; i ++) {
        pt[i] = pt[i-1]*2;
    }
    for (int i = 2; i <= k; i ++) {
        ap[i] = ap[i/2]+1;
    }
    for (int i = 1; i <= ap[k]; i ++) {
        for (int j = 1; j <= k - pt[i-1]; j ++) {
            if (level[rmq[i-1][j]] <= level[rmq[i-1][j+pt[i-1]]]) {
                rmq[i][j] = rmq[i-1][j];
            }
            else {
                rmq[i][j] = rmq[i-1][j+pt[i-1]];
            }
        }
    }
    for (int i = 1; i <= n; i ++) {
        hz[i] = 0;
    }
    dfs_dinamica(1);
    for (int i = 1; i <= ap[n]; i ++) {
        for (int j = 1; j <= n; j ++) {
            stramosi[i][j].first = stramosi[i-1][stramosi[i-1][j].first].first;
            stramosi[i][j].second = min (stramosi[i-1][j].second, stramosi[i-1][stramosi[i-1][j].first].second);
        }
    }
    in >> x >> y >> A >> B >> C >> D;
    for (int i = 1; i <= m; i ++) {
        a = x;
        b = y;
        c = LCA (x,y);
        if ( a != c ){
            dx = level[a] - level[c];
            ad = ap[dx];
            s1 = stramosi[ad][a].second;
            dx -= pt[ad];
            aux = ap[dx];
            num = a;
            aux = 0;
            while (dx) {
                if (dx % 2 == 1) {
                    num = stramosi[aux][num].first;
                }
                dx /= 2;
                aux ++;
            }
            s2 =stramosi[ad][num].second;
            z1 = min (s1,s2);
        }
        else {
            z1 = 1e9;
        }
        if (b != c) {
            dx = level[b] - level[c];
            ad = ap[dx];
            s1 = stramosi[ad][b].second;

            dx -= pt[ad];
            aux = ap[dx];
            num = b;
            aux = 0;
            while (dx) {
                if (dx % 2 == 1) {
                    num = stramosi[aux][num].first;
                }
                dx /= 2;
                aux ++;
            }
            s2 =stramosi[ad][num].second;
            z2 = min (s1,s2);
        }
        else{
            z2 = 1e9;
        }
        z = min (z1,z2);
        if (a == b) {
            z = 0;
        }
        if (i >= m-p+1) {
            out << z <<"\n";
        }
        x = (x*A + y*B) % n + 1;
        y = (y*C + z*D) % n + 1;
    }

    return 0;
}