Cod sursa(job #2697914)

Utilizator dimi999Dimitriu Andrei dimi999 Data 20 ianuarie 2021 13:40:49
Problema Atac Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.79 kb
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};

struct Edges
{
    int dest, cost;
};

ifstream fin("atac.in");
//ofstream fout("atac.out");

vector <Edges> v[32005];

int sz[32005], label[32005], k, level[32005], N;
int head[32005], dads[32005];

void get_size(int node, int dad)
{
    sz[node]++;
    dads[node] = dad;
    level[node] = level[dad] + 1;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad)
    {
        get_size(v[node][i].dest, node);
        sz[node] += sz[v[node][i].dest];
    }
}

void dfsGreu(int node, int dad)
{
    label[node] = ++k;

    int maxi, heavySon = v[node][0].dest;

    if(heavySon == dad && v[node].size() > 1)
        heavySon = v[node][1].dest;

    maxi = sz[heavySon];

    if(v[node].size() == 1 && dad != 0)
        return;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad && sz[v[node][i].dest] > maxi)
            maxi = sz[v[node][i].dest], heavySon = v[node][i].dest;

    head[heavySon] = head[node];
    dfsGreu(heavySon, node);

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad && v[node][i].dest != heavySon)
        dfsGreu(v[node][i].dest, node);

}

int val[32005];

struct Aint
{
    int V[150000];

    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            V[node] = val[st];
            return;
        }

        int mij = (st + dr) / 2;

        build(2 * node, st, mij);
        build(2 * node + 1, mij + 1, dr);

        V[node] = min(V[2 * node], V[2 * node + 1]);
    }

    int query(int node, int st, int dr, int l, int r)
    {
        if(st >= l && dr <= r)
            return V[node];

        if(st > r || dr < l)
            return INT_MAX;

        int mij = (st + dr) / 2;

        return min(query(2 * node, st, mij, l, r),
                   query(2 * node + 1, mij + 1, dr, l, r));
    }
}aint;

void get_val(int node, int cost)
{
    val[label[node]] = cost;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dads[node])
            get_val(v[node][i].dest, v[node][i].cost);
}

int sol(int x, int y)
{
    if(head[x] == head[y])
    {
        int a, b;

        a = label[x];
        b = label[y];

        if(a > b)
            swap(a, b);

        return aint.query(1, 1, N, a + 1, b);
    }

    if(level[head[x]] > level[head[y]])
    {
        int a, b;

        a = label[head[x]];
        b = label[x];

        return min(aint.query(1, 1, N, a, b), sol(dads[head[x]], y));
    }
    else
    {
        int a, b;

        a = label[head[y]];
        b = label[y];

        return min(aint.query(1, 1, N, a, b), sol(x, dads[head[y]]));
    }

}



int main()
{
    OutParser fout("atac.out");
    int M, P;

    fin >> N >> M >> P;

    for(int i = 2; i <= N; i++)
    {
        int x, y;

        fin >> x >> y;

        v[x].push_back({i, y});
        v[i].push_back({x, y});
    }

    get_size(1, 0);

    for(int i = 1; i <= N; i++)
        head[i] = i;

    dfsGreu(1, 0);

    get_val(1, 0);

    aint.build(1, 1, N);

    int A, B, C, D, X, Y;

    fin >> X >> Y >> A >> B >> C >> D;

    while(M != 0)
    {
        int ans;

        if(X == Y)
            ans = 0;
        else
            ans = sol(X, Y);

        if(M <= P)
            fout << ans << '\n';

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + ans * D) % N + 1;
        M--;
    }

    return 0;
}