Pagini recente » Cod sursa (job #2162934) | Cod sursa (job #80111) | Cod sursa (job #1063381) | Cod sursa (job #209128) | Cod sursa (job #3133699)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
using pii = pair<int,int>;
#pragma GCC optimize("Ofast")
class InParser {
vector<char> str;
int ptr;
ifstream fin;
char getChar() {
if (ptr == int(str.size())) {
fin.read(str.data(), str.size());
ptr = 0;
}
return str[ptr++];
}
template<class T>
T getInt() {
char chr = getChar();
while (!isdigit(chr) && chr != '-')
chr = getChar();
int sgn = +1;
if (chr == '-') {
sgn = -1;
chr = getChar();
}
T num = 0;
while (isdigit(chr)) {
num = num * 10 + chr - '0';
chr = getChar();
}
return sgn * num;
}
public:
InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
~InParser() { fin.close(); }
template<class T>
friend InParser& operator>>(InParser& in, T& num) {
num = in.getInt<T>();
return in;
}
};
class OutParser {
vector<char> str;
int ptr;
ofstream fout;
void putChar(char chr) {
if (ptr == int(str.size())) {
fout.write(str.data(), str.size());
ptr = 0;
}
str[ptr++] = chr;
}
template<class T>
void putInt(T num) {
if (num < 0) {
putChar('-');
num *= -1;
}
if (num > 9)
putInt(num / 10);
putChar(num % 10 + '0');
}
public:
OutParser(const char* name) : str(1e5), ptr(0), fout(name) { }
~OutParser() { fout.write(str.data(), ptr); fout.close(); }
template<class T>
friend OutParser& operator<<(OutParser& out, const T num) {
out.putInt(num);
return out;
}
friend OutParser& operator<<(OutParser& out, const char chr) {
out.putChar(chr);
return out;
}
friend OutParser& operator<<(OutParser& out, const char* str) {
for (int i = 0; str[i]; i++)
out.putChar(str[i]);
return out;
}
};
InParser cin("atac.in");
OutParser cout("atac.out");
const int MAX = 64e4+1;
struct muchie{
int x , y , c;
};
bool crit( muchie r , muchie l){
return r.c > l.c;
}
vector <muchie> edges;
int qx , qy , a , b , c , d , n , m , p;
struct DSU{
int h[MAX] , t[MAX] , val[MAX] , ind;
vector <int> g[MAX];
void init(){
for(int i = 1 ; i <= n ; i++){
h[i] = t[i] = val[i] = 0;
}
ind = n+1;
}
int findc( int x ){
while(t[x]) x = t[x];
return x;
}
void unionp( int x , int y , int c){
x = findc(x);
y = findc(y);
if(x == y) return;
t[x] = t[y] = ind;
val[ind] = c;
ind++;
}
int value( int x , int y ){
vector <int> xs;
vector <int> ys;
while(x){
xs.push_back(x);
x=t[x];
}
while(y){
ys.push_back(y);
y=t[y];
}
reverse(xs.begin(),xs.end());
reverse(ys.begin(),ys.end());
int i;
for(i = 0 ; i < (int)xs.size() && i < (int)ys.size() && xs[i]==ys[i]; i++);
return val[xs[i-1]];
}
}uf;
signed main(){
cin >> n >> m >> p;
int x , y;
uf.init();
for(int i = 2 ; i <= n ; i++){
cin >> x >> y;
edges.push_back({x,i,y});
}
sort(edges.begin(),edges.end(),crit);
for(auto it : edges){
uf.unionp(it.x,it.y,it.c);
}
cin >> qx >> qy >> a >> b >> c >> d;
for(int i = 1 ; i <= m ; i++){
int val = uf.value(qx,qy);
if(m - (i-1) <= p){
cout << val << '\n';
}
qx = (qx*a+qy*b)%n + 1;
qy = (qy*c+val*d)%n + 1;
}
return 0;
}