Cod sursa(job #1709827)

Utilizator cristina_borzaCristina Borza cristina_borza Data 28 mai 2016 14:03:30
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <vector>
#include <set>

#define NMAX 32005

using namespace std;

ifstream f("atac.in");
ofstream g("atac.out");

int r[NMAX][25] , t[NMAX][25] , log[NMAX] , tata[NMAX] , cost[NMAX] , nivel[NMAX];
int n , m , x , y , sol , a , b , c , d , p;

vector <vector <pair <int , int> > > v;

void dfs(int node , int tt);

int minim(int node1 , int node2);
int solve(int x , int y);

int main() {
    f >> n >> m >> p;

    v.resize(n + 2);
    for(int i = 2 ; i <= n ; ++i) {
        f >> y >> c;
        x = i;

        v[x].push_back(make_pair(y , c));
        v[y].push_back(make_pair(x , c));
    }

    nivel[1] = 1;
    dfs(1 , -1);
    for(int i = 1 ; i <= n ; ++i) {
        t[i][0] = tata[i];
        r[i][0] = cost[i];
        for(int j = 1 ; (1 << j) <= nivel[i] ; ++j) {
            t[i][j] = t[t[i][j - 1]][j - 1];
            r[i][j] = min(r[i][j - 1] , r[t[i][j - 1]][j - 1]);
        }
    }

    for(int i = 1 ; i <= n ; ++i) {
        int aux = 1;
        while((1 << aux) <= i) {
            ++aux;
        }

        log[i] = aux - 1;
    }

    f >> x >> y >> a >> b >> c >> d;
    for(int i = 1 ; i <= m; ++i) {
        int z = solve(x , y);
        if(x == y)
            z = 0;
        int xx = (x * a + y * b) % n + 1;
        int yy = (y * c + z * d) % n + 1;

        x = xx;
        y = yy;

        if(i > m - p)
            g << z << '\n';
    }
    return 0;
}

int solve(int x , int y) {
    int xx = x;
    int yy = y;
    if(nivel[x] < nivel[y]) {
        swap(x , y);
    }

    int dif = nivel[x] - nivel[y];
    int j = 0;

    while(dif) {
        if(dif % 2 != 0) {
            x = t[x][j];
        }

        ++j;
        dif /= 2;
    }

    if(x == y) {
        return x;
    }

    int pas = log[nivel[x]];
    while(pas) {
        if(t[x][pas] != t[y][pas]) {
            x = t[x][pas];
            y = t[y][pas];
        }
        --pas;
    }

    if(t[x][pas] != t[y][pas]) {
        x = t[x][pas];
        y = t[y][pas];
    }

    return min(minim(xx , t[x][0]) , minim(yy , t[x][0]));
}

int minim(int x , int y) {
    int ans = 1000000 , aux = nivel[x] - nivel[y] , step;
    for(step = 0 ; (1<<(step + 1)) <= aux; ++step);
    for(; step >= 0 && aux > 0; --step ) {
        if(nivel[t[x][step]] >= nivel[y]) {
            ans = min(ans , r[x][step]);
            x = t[x][step];
        }
    }

    return ans;
}

void dfs(int node , int tt) {
    if(node != 1) {
        nivel[node] = 1 + nivel[tt];
    }

    for(int it = 0 ; it < v[node].size() ; ++it) {
        if(v[node][it].first != tt) {
            cost[v[node][it].first] = v[node][it].second;
            tata[v[node][it].first] = node;
            dfs(v[node][it].first , node);
        }
    }
}