Cod sursa(job #2644340)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 24 august 2020 12:22:07
Problema Atac Scor 20
Compilator cpp-64 Status done
Runda prbd2 Marime 2.38 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ifstream fin("atac.in");
ofstream fout("atac.out");
int t,n,m,p,lev[32001],dp[32001][51];
ll x,y,a,b,c,d,z=-1;
vector<pii> muchie[33001];
int memo[32001][51];
bool use[1001];
void dfs(int nod,int parent)
{
    use[nod]=1;
    if(parent>0)
        memo[nod][0]=parent;
    for(int i=1;i<=20;i++)
    {
        memo[nod][i]=memo[memo[nod][i-1]][i-1];
        dp[nod][i]=min(dp[nod][i-1],dp[memo[nod][i-1]][i-1]);
    }
    for(auto i:muchie[nod])
    {
        if(!use[i.first])
        {
            lev[i.first]=lev[nod]+1;
            dp[i.first][0]=i.second;
            dfs(i.first,nod);
        }
    }
}
int lca(int u, int v)
{
    if (lev[u] < lev[v])
        swap(u, v);
    for (int i = 20; i >= 0; i--)
        if ((lev[u] - pow(2, i)) >= lev[v])
            u = memo[u][i];
    if (u == v)
        return u;
    for (int i = 20; i >= 0; i--)
    {
        if (memo[u][i] != memo[v][i])
        {
            u = memo[u][i];
            v = memo[v][i];
        }
    }
    return memo[u][0];
}
ll cost(ll nod,ll nr)
{
    int ans=1e9;
    for(int bit=0;bit<=20;bit++)
        if((nr>>bit)&1)
        {
            ans=min(ans,dp[nod][bit]);
            nod=memo[nod][bit];
        }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>n>>m>>p;
    for(int i=2;i<=n;i++)
    {
        int u,v;
        fin>>u>>v;
        muchie[u].push_back({i,v});
        muchie[i].push_back({u,v});
    }
    fin>>x>>y>>a>>b>>c>>d;
    dfs(1,0);
    while(m--)
    {
        if(z!=-1)
        {
            x=(x*a+y*b)%n+1;
            y=(y*c+z*d)%n+1;
        }
        if(x==y)
            z=0;
        else
        {
            int stramos=lca(x,y);
            int niv1=lev[x]-lev[stramos];
            int niv2=lev[y]-lev[stramos];
            z=min(cost(x,niv1),cost(y,niv2));
        }
        if(m<p)
            fout<<z<<'\n';
    }
    return 0;
}