Cod sursa(job #3133699)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 26 mai 2023 16:42:21
Problema Atac Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.96 kb
#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;
}