Pagini recente » Cod sursa (job #517158) | Cod sursa (job #1868788) | Cod sursa (job #800701) | Cod sursa (job #2558983) | Cod sursa (job #2240961)
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int NMAX = 32 * 1e3;
const int INF = 1 << 30;
struct Edge {
int x;
int y;
int cost;
bool operator< (Edge other) const {
return other.cost < cost;
}
};
int n, m, k;
int cost[1 + NMAX];
int sef[1 + NMAX];
int level[1 + NMAX];
Edge g[1 + NMAX];
int get_sef(int el) {
while(el != sef[el])
el = sef[el];
return el;
}
int get_level(int el) {
if(el == sef[el])
return 0;
get_level(sef[el]);
level[el] = level[sef[el]] + 1;
}
int main()
{
in >> n >> m >> k;
for(int i = 1; i < n; i++) {
g[i].x = i + 1;
in >> g[i].y >> g[i].cost;
}
for(int i = 1; i <= n; i++)
sef[i] = i;
sort(g + 1, g + n);
for(int i = 1; i < n; i++) {
int p1 = get_sef(g[i].x);
int p2 = get_sef(g[i].y);
if(p1 != p2) {
sef[p1] = p2;
cost[p1] = g[i].cost;
}
}
for(int i = 1; i <= n; i++) {
if(level[i] == 0)
get_level(i);
}
int x, y, a, b, c, d;
in >> x >> y >> a >> b >> c >> d;
for(int zz = 1; zz <= m; zz++) {
int p1 = x;
int p2 = y;
int minn = INF;
while(level[x] > level[y]) {
minn = min(minn, cost[x]);
x = sef[x];
}
while(level[y] > level[x]) {
minn = min(minn, cost[y]);
y = sef[y];
}
while(x != y) {
minn = min(minn, min(cost[x], cost[y]));
x = sef[x];
y = sef[y];
}
if(minn == INF)
minn = 0;
if(m - zz + 1 <= k)
out << minn << '\n';
x = (p1 * a + p2 * b) % n + 1;
y = (p2 * c + minn * d) % n + 1;
}
in.close();
out.close();
return 0;
}