Cod sursa(job #2852747)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 19 februarie 2022 14:39:50
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

const int NMAX = 32000 + 5;
const int LOG = 16;

int N, M, P;
int x, y, a, b, c, d;

struct elem
{
    int nod, cost;
};

vector<elem> g[NMAX];
int depth[NMAX];
int up[NMAX][LOG];
int rmqMin[NMAX][LOG];
vector<int> answers;

void dfs(int fiu, int tata)
{
    depth[fiu] = 1 + depth[tata];
    for(int i = 1; i < LOG; i ++)
    {
        up[fiu][i] = up[up[fiu][i - 1]][i - 1];
    }
    for(int i = 1; i < LOG; i ++)
    {
        rmqMin[fiu][i] = min(rmqMin[fiu][i - 1], rmqMin[up[fiu][i - 1]][i - 1]);
    }
    for(auto it : g[fiu])
    {
        if(it.nod != tata)
        {
            up[it.nod][0] = fiu;
            rmqMin[it.nod][0] = it.cost;
            dfs(it.nod, fiu);
        }
    }
}

int query(int x, int y)
{
    if(depth[x] < depth[y])
    {
        swap(x, y);
    }
    int dif = depth[x] - depth[y];
    int ans = (1 << 30);
    for(int i = LOG - 1; i >= 0; i --)
    {
        if(dif & (1 << i))
        {
            ans = min(ans, rmqMin[x][i]);
            x = up[x][i];
        }
    }
    if(x == y)
    {
        return ans;
    }
    for(int i = LOG - 1; i >= 0; i --)
    {
        if(up[x][i] != up[y][i])
        {
            ans = min(ans, rmqMin[x][i]);
            ans = min(ans, rmqMin[y][i]);
            x = up[x][i];
            y = up[y][i];
        }
    }
    ans = min(ans, min(rmqMin[x][0], rmqMin[y][0]));
    return ans;
}

int main()
{
    fin >> N >> M >> P;
    for(int i = 2; i <= N; i ++)
    {
        int u, v;
        fin >> u >> v;
        g[u].push_back({i, v});
        g[i].push_back({u, v});
    }
    dfs(1, 0);
    fin >> x >> y >> a >> b >> c >> d;
    for(int i = 2; i <= M; i ++)
    {
        int z;
        if(x == y)
        {
            z = 0;
        }
        else
        {
            z = query(x, y);
        }
        answers.push_back(z);
        x = (x * a + y * b) % N + 1;
        y = (y * c + z * d) % N + 1;
    }
    for(int i = answers.size() - P; i < answers.size(); i ++)
    {
        fout << answers[i] << '\n';
    }
    return 0;
}