Cod sursa(job #1709223)

Utilizator cristina_borzaCristina Borza cristina_borza Data 28 mai 2016 11:21:30
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 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 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 <= 2 * 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);
        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 mn = 500000;
    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];
            mn = min(mn , r[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];

            mn = min(mn , r[x][pas]);
            mn = min(mn , r[y][pas]);
        }
        --pas;
    }

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

        mn = min(mn , r[x][pas]);
        mn = min(mn , r[y][pas]);
    }

    mn = min(mn , r[x][0]);
    mn = min(mn , r[y][0]);
    return mn;
}

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);
        }
    }
}