Cod sursa(job #1114360)

Utilizator SmarandaMaria Pandele Smaranda Data 21 februarie 2014 15:51:10
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 32005;
const int MAX_INT = 2147000000;
typedef pair<int, int> pere;

vector<pere> tree[MAX_N];
int min_on_chain[17][MAX_N];
int ancestor[17][MAX_N];
int level[MAX_N];

void dfs(int node, int father, int edge_cost) {
    ancestor[0][node] = father;
    level[node] = level[father] + 1;
    min_on_chain[0][node] = edge_cost;
    for(vector<pere> :: iterator it = tree[node].begin(); it != tree[node].end(); ++ it) {
        if(it->first != father) {
            dfs(it->first, node, it->second);
        }
    }
}

inline int get_lca(int x, int y) {
    if(level[x] < level[y]) {
        swap(x, y);
    }
    for(int pace = 15; pace >= 0; -- pace) {
        if(level[ancestor[pace][x]] >= level[y]) {
            x = ancestor[pace][x];
        }
    }
    if(x == y) {
        return x;
    }
    for(int pace = 15; pace >= 0; -- pace) {
        if(ancestor[pace][x] != ancestor[pace][y]) {
            x = ancestor[pace][x];
            y = ancestor[pace][y];
        }
    }
    return ancestor[0][x];
}
inline int solve_to_ancestor(int x, int y) {
    int answer = MAX_INT;
    for(int pace = 15; pace >= 0; -- pace) {
        if(level[ancestor[pace][x]] >= level[y]) {
            answer = min(answer, min_on_chain[pace][x]);
            x = ancestor[pace][x];
        }
    }
    return answer;
}
inline int solve(int x, int y) {
    int lca = get_lca(x, y);
    return min(solve_to_ancestor(x, lca), solve_to_ancestor(y, lca));
}

int main() {
    ifstream fin("atac.in");
    ofstream fout("atac.out");
    int n, m, p;
    fin >> n >> m >> p;
    for(int i = 2; i <= n; ++ i) {
        int x, cost;
        fin >> x >> cost;
        tree[x].push_back(pere(i, cost));
        tree[i].push_back(pere(x, cost));
    }
    dfs(1, 0, MAX_INT);
    for(int i = 1; (1 << i) <= n; ++ i) {
        for(int j = 1; j <= n; ++ j) {
            ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
            min_on_chain[i][j] = min(min_on_chain[i - 1][j], min_on_chain[i - 1][ancestor[i - 1][j]]);
        }
    }
    int x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;
    for(int i = 1; i <= m; ++ i) {
        int k = solve(x, y);
        if(i >= m - p + 1) {
            fout << k << "\n";
        }
        int new_x = (x * a + y * b) % n + 1;
        int new_y = (y * c + k * d) % n + 1;
        x = new_x;
        y = new_y;
    }
    return 0;
}