Pagini recente » Istoria paginii runda/dr_strangelove/clasament | Cod sursa (job #1865398) | Istoria paginii runda/preoji_bv_2017_1_1112/clasament | Cod sursa (job #215651) | Cod sursa (job #1114409)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 32005;
const int MAX_INT = 2147000000;
typedef pair<int, int> pere;
vector<pere> tree[MAX_N];
int min_on_chain[17][MAX_N];
int ancestor[17][MAX_N];
int level[MAX_N];
void dfs(int node, int father, int edge_cost) {
ancestor[0][node] = father;
level[node] = level[father] + 1;
min_on_chain[0][node] = edge_cost;
for(vector<pere> :: iterator it = tree[node].begin(); it != tree[node].end(); ++ it) {
if(it->first != father) {
dfs(it->first, node, it->second);
}
}
}
inline int solve(int x, int y) {
int answer = MAX_INT;
if(level[x] < level[y]) {
swap(x, y);
}
for(int pace = 15; pace >= 0; -- pace) {
if(level[ancestor[pace][x]] >= level[y]) {
answer = min(answer, min_on_chain[pace][x]);
x = ancestor[pace][x];
}
}
if(x == y) {
return answer;
}
for(int pace = 15; pace >= 0; -- pace) {
if(ancestor[pace][x] != ancestor[pace][y]) {
answer = min(answer, min_on_chain[pace][x]);
answer = min(answer, min_on_chain[pace][y]);
x = ancestor[pace][x];
y = ancestor[pace][y];
}
}
answer = min(answer, min_on_chain[0][x]);
answer = min(answer, min_on_chain[0][y]);
return answer;
}
class OutputWriter {
public:
OutputWriter(const char *out_file) {
file = fopen(out_file, "w");
}
inline OutputWriter &operator<<(const int &number) {
char p[15];
int copy = number, digits = 0;
do {
p[digits ++] = '0' + copy % 10;
copy /= 10;
}while(copy);
for(int i = digits - 1; i >= 0; -- i) {
(*this) << p[i];
}
return *this;
}
inline OutputWriter &operator<<(const char &ch) {
buffer[cursor ++] = ch;
if(cursor == size) {
cursor = 0;
fwrite(buffer, size, 1, file);
}
return *this;
}
inline void flush() {
fwrite(buffer, cursor, 1, file);
cursor = 0;
}
private:
FILE *file;
const static int MAX_BUFFER_SIZE = 1 << 15;
int cursor, size;
char buffer[MAX_BUFFER_SIZE];
};
int main() {
ifstream fin("atac.in");
OutputWriter fout("atac.out");
int n, m, p;
fin >> n >> m >> p;
for(int i = 2; i <= n; ++ i) {
int x, cost;
fin >> x >> cost;
tree[x].push_back(pere(i, cost));
tree[i].push_back(pere(x, cost));
}
dfs(1, 0, MAX_INT);
for(int i = 1; (1 << i) <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
min_on_chain[i][j] = min(min_on_chain[i - 1][j], min_on_chain[i - 1][ancestor[i - 1][j]]);
}
}
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for(int i = 1; i <= m; ++ i) {
int k = solve(x, y);
if(k == MAX_INT) {
k = 0;
}
if(i >= m - p + 1) {
fout << k << '\n';
}
int new_x = (x * a + y * b) % n + 1;
int new_y = (y * c + k * d) % n + 1;
x = new_x;
y = new_y;
}
fout.flush();
return 0;
}