Cod sursa(job #2351982)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 22 februarie 2019 21:06:44
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;

class RMQ {
 private:
    vector < int > logVec;
    vector < vector < int > > rmqVec;

 public:
    RMQ(vector < int > _RMQ){
        logVec.assign(_RMQ.size() + 1, 0);
        for (int i = 2; i < logVec.size(); i++) {
            logVec[i] = logVec[i / 2] + 1;
        }

        rmqVec.assign(logVec.back() + 1, vector < int >(_RMQ.size()));
        rmqVec[0] = _RMQ;

        for (int logX = 1; logX < rmqVec.size(); logX++) {
            for (int i = 0; i + (1 << logX) <= _RMQ.size(); i++) {
                rmqVec[logX][i] = min(rmqVec[logX - 1][i], rmqVec[logX - 1][i + (1 << (logX - 1))]);
            }
        }
    }

    int getMin(int l, int r) { // ! returns the answer for the interval [l, r) !
        int logX = logVec[r - l];
        return min(rmqVec[logX][l], rmqVec[logX][r - (1 << logX)]);
    }
};

int n, m, p, k, a, b, c, d, x, y, dp[16][1 << 15], lvl[1 << 15], mn[16][1 << 15];

vector < int > bck;
vector < int > fst;
vector < int > euler;
vector < PII > V[1 << 15];

void eulerTour(int curr, int dad, int l) {
    lvl[curr] = l;
    int newIndex = bck.size();
    bck.push_back(curr);
    fst[curr] = euler.size();
    euler.push_back(newIndex);

    for (int i = 1; i <= 15; i++) {
        dp[i][curr] = dp[i - 1][dp[i - 1][curr]];
        mn[i][curr] = min(mn[i - 1][curr], mn[i - 1][dp[i - 1][curr]]);
    }

    for (auto it : V[curr]) {
        if (it.first == dad) continue;

        eulerTour(it.first, curr, l + 1);
        euler.push_back(newIndex);
    }
}

int main(){
    ifstream cin("atac.in");
    ofstream cout("atac.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> p;

    for (int i = 1; i <= 15; i++) {
        for (int j = 1; j <= n; j++) {
            mn[i][j] = INT_MAX;
        }
    }

    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        V[x].push_back({i + 1, y});
        mn[0][i + 1] = y;
        dp[0][i + 1] = x;
    }

    cin >> x >> y >> a >> b >> c >> d;

    fst.assign(n + 1, -1);
    eulerTour(1, 1, 1);

    RMQ rmq(euler);

    int ans;
    for (int i = 1; i <= m; i++) {
        int nodeX = fst[x], nodeY = fst[y];
        if (nodeX > nodeY) swap(nodeX, nodeY);
        int cpx = x, cpy = y;

        if (nodeX == nodeY) {
            ans = 0;
            x = (cpx * a + cpy * b) % n + 1;
            y = (cpy * c + ans * d) % n + 1;

            if (m - i + 1 <= p)
                cout << ans << "\n";
            
            continue;
        }

        int newIndex = rmq.getMin(nodeX, nodeY + 1);
        int oldIndex = bck[newIndex];
        ans = INT_MAX;

        int diff = lvl[x] - lvl[oldIndex];

        while (diff) {
            int lg = log2(diff);
 
            ans = min(ans, mn[lg][x]);
            x = dp[lg][x];
 
            diff -= (1 << lg);
        }

        diff = lvl[y] - lvl[oldIndex];

        while (diff) {
            int lg = log2(diff);
 
            ans = min(ans, mn[lg][y]);
            y = dp[lg][y];
 
            diff -= (1 << lg);
        }

        x = (cpx * a + cpy * b) % n + 1;
        y = (cpy * c + ans * d) % n + 1;

        if (m - i + 1 <= p)
            cout << ans << "\n";
    }
	return 0;
}