Cod sursa(job #1536103)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 25 noiembrie 2015 18:31:27
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 32000;
const int kMaxLog = 15;

vector <pair<int, int>> adj[kMaxN];
int d[kMaxLog][kMaxN];
int c[kMaxLog][kMaxN];
int depth[kMaxN];

void DFS(int u) {
    for (auto son : adj[u]) {
        if (!depth[son.first]) {
            depth[son.first] = depth[u] + 1;
            d[0][son.first] = u;
            c[0][son.first] = son.second;
            DFS(son.first);
        }
    }
}

int main(void) {
    ifstream in("atac.in");
    ofstream out("atac.out");
    in.tie(0);
    ios_base::sync_with_stdio(0);
    int N, Q, P;
    int U, V, A, B, C, D;

    in >> N >> Q >> P;
    for (int i = 1; i < N; i++) {
        in >> U >> V;
        adj[U - 1].emplace_back(make_pair(i, V));
        adj[i].emplace_back(make_pair(U - 1, V));
    }
    in >> U >> V >> A >> B >> C >> D;
    in.close();

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

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

    auto solveQuery = [] (int u, int v) -> int {
        auto fastLg = [] (const int &X) -> int {
            return 31 - __builtin_clz(X);
        };
        if (u == v) {
            return 0;
        }
        if (depth[u] > depth[v]) {
            swap(u, v);
        }
        int q = numeric_limits <int> :: max();
        for (int k = fastLg(depth[v]); k >= 0; k--) {
            if (depth[u] + (1 << k) <= depth[v]) {
                q = min(q, c[k][v]);
                v = d[k][v];
            }
        }
        if (u != v) {
            for (int k = fastLg(depth[u]); k >= 0; k--) {
                if (d[k][u] && d[k][u] != d[k][v]) {
                    q = min(q, min(c[k][u], c[k][v]));
                    u = d[k][u]; v = d[k][v];
                }
            }
            q = min(q, min(c[0][u], c[0][v]));
        }
        return q;
    };

    while (Q--) {
        int ans = solveQuery(U - 1, V - 1);
        if (Q < P) {
            out << ans << '\n';
        }
        U = (U * A + V * B) % N + 1;
        V = (V * C + ans * D) % N + 1;
    }
    out.close();
    return 0;
}