Mai intai trebuie sa te autentifici.
Cod sursa(job #587792)
Utilizator | Data | 5 mai 2011 21:33:40 | |
---|---|---|---|
Problema | Atac | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.89 kb |
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 32010
int n, m, pp, t[20][nmax], cm[20][nmax], l[nmax], lm, e[nmax<<1], h, r[20][nmax<<1], f[nmax], lg[nmax<<1], lev[nmax<<1];
vector <pair<int, int> > g[nmax];
inline void df(int nod)
{
int i, v;
e[++h]=nod;
lev[h]=l[nod];
f[nod]=h;
for (i=0; i<g[nod].size(); i++)
{
v=g[nod][i].first;
if (!l[v])
{
t[0][v]=nod;
l[v]=l[nod]+1;
cm[0][v]=g[nod][i].second;
if (l[v]>lm) lm=l[v];
df(v);
e[++h]=nod;
lev[h]=l[nod];
}
}
}
inline void rmq()
{
int i, j;
for (i=2; i<=h; i++) lg[i]=lg[i>>1]+1;
for (i=1; i<=h; i++) r[0][i]=i;
for (i=1; (1<<i)<h; i++)
for (j=1; j<=h-(1<<i)+1; j++)
if (lev[r[i-1][j]]<lev[r[i-1][j+(1<<(i-1))]])
r[i][j]=r[i-1][j]; else
r[i][j]=r[i-1][j+(1<<(i-1))];
}
inline int lca(int x, int y)
{
x=f[x];
y=f[y];
if (x>y) swap(x, y);
int d=lg[y-x+1];
if (lev[r[d][x]]<lev[r[d][y-(1<<d)+1]])
return e[r[d][x]]; else
return e[r[d][y-(1<<d)+1]];
}
inline int search(int x, int y)
{
if (x==y) return 1<<30;
int d=lg[l[x]-l[y]];
if (l[t[d][x]]==l[y]) return cm[d][x]; else
return min(cm[d][x], search(t[d][x], y));
}
int main()
{
freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
scanf("%d %d %d", &n, &m, &pp);
int i, j, x, y, a, b, c, d, z, p;
for (i=1; i<n; i++)
{
scanf("%d %d", &x, &y);
g[x].push_back(make_pair(i+1, y));
g[i+1].push_back(make_pair(x, y));
}
l[1]=1;
df(1);
for (i=1; (1<<i)<=lm; i++)
for (j=1; j<=n; j++)
{
t[i][j]=t[i-1][t[i-1][j]];
if (t[i][j]) cm[i][j]=min(cm[i-1][j], cm[i-1][t[i-1][j]]);
}
rmq();
scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
while (m--)
{
if (x==y) z=0; else
{
p=lca(x,y);
z=min(search(x, p), search(y, p));
}
if (m<pp) printf("%d\n",z);
x=(x*a+y*b)%n+1;
y=(y*c+z*d)%n+1;
}
}