Cod sursa(job #2644563)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 24 august 2020 22:14:25
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define qwerty1 first
#define qwerty2 second
#define qwerty3 -> first
#define qwerty4 -> second
#define umap unordered_map
#define uset unordered_set
#define pii pair < int , int >
#define pq priority_queue
#define dbg(x) cerr << #x << ": " << x << '\n'

using namespace std;

const int N = 32005;
const int M = 1e9 + 7;
const ld PI = acos(-1);

int n , u , v , m , p , X , Y , A , B , C , D;
vector < int > g[N];
int d[N] , par[N] , f[N][20] , e[N][20];
map < pii , int > edge;

void dfs(int u , int ant , int lev)
{
    d[u] = lev;
    par[u] = ant;

    for(auto i : g[u])
        if(i != ant)
            dfs(i , u , lev + 1);
}

void anc()
{
    int i , j;

    for(i = 1 ; i <= n ; i++)
        f[i][0] = par[i];

    for(j = 1 ; (1 << j) <= n ; j++)
        for(i = 1 ; i <= n ; i++)
            f[i][j] = f[ f[i][j - 1] ][j - 1];
}

void bnl()
{
    int i , j;

    e[1][0] = INT_MAX;

    for(i = 2 ; i <= n ; i++)
        e[i][0] = edge[{i , par[i]}];

     for(j = 1 ; (1 << j) <= n ; j++)
        for(i = 1 ; i <= n ; i++)
            e[i][j] = INT_MAX;

     for(j = 1 ; (1 << j) <= n ; j++)
        for(i = 1 ; i <= n ; i++)
            e[i][j] = min(e[i][j - 1] , e[ f[i][j - 1] ][j - 1]);
}

int getmin(int x , int y)
{
    if(x == y)
        return 0;

     if(d[x] < d[y])
        swap(x , y);

    int ans = INT_MAX , up = d[x] - d[y];
    int U = log2(up);

    for(int bit = 0 ; bit <= U ; bit++)
        if(up >> bit & 1)
        {
            ans = min(ans , e[x][bit]);
            x = f[x][bit];
        }

    if(x == y)
        return ans;

    int l = log2(d[y]) + 1;

    for(int i = l ; i >= 0 ; i--)
        if(f[x][i] != f[y][i])
        {
            ans = min({ans , e[x][i] , e[y][i]});
            x = f[x][i];
            y = f[y][i];
        }

    return min({ans , e[y][0] , e[x][0]});
}

signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("atac.in" , "r" , stdin) , freopen("atac.out" , "w" , stdout);
	#endif

	ios_base::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);

    int i;

    cin >> n >> m >> p;

    for(i = 2 ; i <= n ; i++)
    {
        cin >> u >> v;

        g[u].pb(i);
        g[i].pb(u);
        edge[{u , i}] = edge[{i , u}] = v;
    }

    dfs(1 , 1 , 0);
    anc();
    bnl();

    cin >> X >> Y >> A >> B >> C >> D;

    int Z = getmin(X , Y);

    for(i = 1 ; i <= m ; i++)
    {
        X = (X * A + Y * B) % n + 1;
        Y = (Y * C + Z * D) % n + 1;

        if(m - i + 1 <= p)
            cout << Z << '\n';

        Z = getmin(X , Y);
    }

    return 0;
}