Mai intai trebuie sa te autentifici.
Cod sursa(job #1386768)
Utilizator | Data | 13 martie 2015 11:15:26 | |
---|---|---|---|
Problema | Atac | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.91 kb |
/*
Keep It Simple!
*/
#include <fstream>
#include <vector>
using namespace std;
const int kMaxN = 32005;
const int kMaxLb = 17;
const int kInf = 0x3f3f3f3f;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
ifstream fin("atac.in");
ofstream fout("atac.out");
int N,M,P;
vector<pii> G[kMaxN];
long long X,Y,A,B,C,D;
int lb[kMaxN << 1],lvl[kMaxN],first[kMaxN];
int rmq[kMaxLb][kMaxN << 1];
pii dp[kMaxLb][kMaxN];
int euler_sz;
bool used[kMaxN];
void ReadInput()
{
int x,y;
fin >> N >> M >> P;
for(int i=2; i<=N; ++i)
{
fin >> x >> y;
G[i].pb(mp(x,y));
G[x].pb(mp(i,y));
}
fin >> X >> Y >> A >> B >> C >> D;
}
void ComputeLb()
{
for(int i=2; i< (kMaxN<<1); ++i)
lb[i] = lb[i>>1]+1;
}
void DFS(int node,int lv)
{
rmq[0][++euler_sz] = node;
first[node] = euler_sz;
used[node] = true;
for(auto it:G[node])
if(!used[it.fi])
{
dp[0][it.fi] = mp(node,it.se);
lvl[it.fi] = lv+1;
DFS(it.fi,lv+1);
rmq[0][++euler_sz] = node;
}
}
int MinLvl(int a,int b)
{
if(lvl[a] < lvl[b])
return a;
return b;
}
void ComputeDynamics()
{
for(int i=1; i<kMaxLb; ++i)
for(int j=1; j<=N; ++j)
dp[i][j].fi = -1;
for(int i=1; i<kMaxLb; ++i)
{
for(int j=1; j<=N; ++j)
if(dp[i-1][j].fi != -1)
{
dp[i][j].fi = dp[i-1][dp[i-1][j].fi].fi;
dp[i][j].se = min(dp[i-1][j].se,dp[i-1][dp[i-1][j].fi].se);
}
for(int j=1; j + (1<<i) <= euler_sz; ++j)
rmq[i][j] = MinLvl(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
}
void ComputeData()
{
lvl[1] = 1;
DFS(1,1);
ComputeLb();
ComputeDynamics();
}
int FindLca(int x,int y)
{
int a = first[x],b=first[y];
if(a > b) swap(a,b);
int len = lb[b-a];
return MinLvl(rmq[len][a],rmq[len][b-(1<<len)+1]);
}
int MinEdge(int x,int y)
{
int ans = kInf;
int diff = lvl[x]-lvl[y];
for(int i=0; i<kMaxLb; ++i)
if(diff & (1<<i))
{
ans = min(ans,dp[i][x].se);
x = dp[i][x].fi;
}
return ans;
}
int Query(int x,int y)
{
if(x == y) return 0;
int lca = FindLca(x,y);
return min(MinEdge(x,lca),MinEdge(y,lca));
}
void PrintQueries()
{
long long ans;
while(M--)
{
ans = Query(X,Y);
if(P > M)
fout << ans << '\n';
X = (X*A + Y*B)%N + 1;
Y = (Y*C + ans*D)%N + 1;
}
}
void Solve()
{
ReadInput();
ComputeData();
PrintQueries();
}
int main()
{
Solve();
return 0;
}