Cod sursa(job #1651249)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 12 martie 2016 20:43:21
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define pii pair< int, int >
#define st first
#define nd second

using namespace std;

const int Mn = 1 << 17;
const int Mlg = 17;
const int oo = 1 << 30;

int n, m, p, x, y, a, b, c, d, cnt;
int lg[Mn], depth[Mn], pos[Mn];
int rmq[Mlg][Mn];
bool used[Mn];
pii parent[Mlg][Mn];
vector< pii > g[Mn];

ifstream fi("atac.in");
ofstream fo("atac.out");

void dfs(int x)
{
    used[x] = 1;
    rmq[0][++cnt] = x;
    pos[x] = cnt;
    for (auto node : g[x])
        if (!used[node.st])
        {
            depth[node.st] = depth[x] + 1;
            parent[0][node.st] = pii(x, node.nd);
            dfs(node.st);
            rmq[0][++cnt] = x;
        }
}

int min_depth(int u, int v)
{
    return (depth[u] < depth[v] ? u : v);
}

int lca(int u, int v)
{
    u = pos[u];
    v = pos[v];
    if (u > v)
       swap(u, v);

    int aux = lg[v - u];
    return min_depth(rmq[aux][u], rmq[aux][v - (1 << aux) + 1]);
}

int min_value(int u, int v)
{
    int aux = depth[u] - depth[v], sol = oo;
    for (int i = 0; i < Mlg; i++)
        if (aux & (1 << i))
           sol = min(sol, parent[i][u].nd), u = parent[i][u].st;

    return sol;
}

int main()
{
    fi >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        int u, v;
        fi >> u >> v;
        g[i].push_back(pii(u, v));
        g[u].push_back(pii(i, v));
    }

    for (int i = 2; i < Mn; i++)
        lg[i] = lg[i / 2] + 1;

    depth[1] = 1;
    dfs(1);
    for (int i = 1; i < Mlg; i++)
    {
        for (int j = 1; j <= cnt - (1 << i) + 1; j++)
            rmq[i][j] = min_depth(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);

        for (int j = 1; j <= n; j++)
        {
            parent[i][j].st = parent[i - 1][parent[i - 1][j].st].st;
            parent[i][j].nd = min(parent[i - 1][j].nd, parent[i - 1][parent[i - 1][j].st].nd);
        }
    }

    fi >> x >> y >> a >> b >> c >> d;
    while (m--)
    {
        int anc = lca(x, y), ans = (x == y ? 0 : min(min_value(x, anc), min_value(y, anc)));
        if (m < p)
           fo << ans << "\n";

        x = (x * a + y * b) % n + 1;
        y = (y * c + ans * d) % n + 1;
    }

    return 0;
}