Cod sursa(job #1535989)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 25 noiembrie 2015 15:26:38
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 32000;
const int kMaxLog = 15;
const int NIL = -1;

struct Edge {
    int v;
    int next;
};

Edge l[kMaxN - 1];
int adj[kMaxN];
int d[kMaxLog][kMaxN];
int c[kMaxLog][kMaxN];
int depth[kMaxN];

void DFS(int u) {
    for (int i = adj[u]; i != NIL; i = l[i].next) {
        depth[l[i].v] = depth[u] + 1;
        DFS(l[i].v);
    }
}

int main(void) {
    ifstream in("atac.in");
    ofstream out("atac.out");
    in.tie(0);
    ios_base::sync_with_stdio(0);
    int N, Q, printQuery;
    int u, v, A, B, C, D;
    int oldU, oldV;

    in >> N >> Q >> printQuery;

    for (int i = 0; i < N; i++) {
        adj[i] = NIL;
    }
    for (int i = 1; i < N; i++) {
        auto addEdge = [] (const int &U, const int &V, const int &ptr) -> void {
            l[ptr].v = V;
            l[ptr].next = adj[U];
            adj[U] = ptr;
        };
        in >> u >> c[0][i];
        d[0][i] = u - 1;
        addEdge(u - 1, i, i - 1);
    }

    depth[0] = 1;
    DFS(0);

    for (int i = 1; (1 << i) <= N; i++) {
        for (int j = 1; j < N; j++) {
            int ancestor = d[i - 1][j];
            c[i][j] = min(c[i - 1][ancestor], c[i - 1][j]);
            d[i][j] = d[i][ancestor]; // kappa
        }
    }

    in >> u >> v >> A >> B >> C >> D;
    in.close();

    while (Q--) {
        auto fastLg = [] (const int &X) {
            return 31 - __builtin_clz(X);
        };
        oldU = u;
        oldV = v;
        u--;
        v--;
        if (depth[u] > depth[v]) {
            swap(u, v);
        }
        int minCost = 0;
        if (u != v) {
            minCost = numeric_limits <int> :: max();
            for (int k = fastLg(depth[v]); k >= 0; k--) {
                if (depth[v] - (1 << k) >= depth[u]) {
                    minCost = min(c[k][v], minCost);
                    v = d[k][v];
                }
            }
            for (int k = fastLg(depth[u]); k >= 0; k--) {
                if (d[k][u] && d[k][u] != d[k][v]) {
                    minCost = min(min(c[k][u], c[k][v]), u);
                    u = d[k][u];
                    v = d[k][v];
                }
            }
            minCost = min(min(c[0][u], c[0][v]), minCost);
        }
        if (Q < printQuery) {
            out << minCost << '\n';
        }
        u = (oldU * A + oldV * B) % N + 1;
        v = (oldV * C + minCost * D) % N + 1;
    }
    out.close();
    return 0;
}