Cod sursa(job #2577214)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 8 martie 2020 18:06:28
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

struct Query {
    int a, b, c;
    Query(int a, int b, int c) :
        a(a), b(b), c(c) { }
};

class Forest {
  private:
    vector<int> height;
    vector<int> father;
    vector<int> nxtPos;

  public:
    Forest(int n) :
        height(n + 1),
        father(n + 1),
        nxtPos(n + 1) {
            for (int i = 1; i <= n; i++)
                nxtPos[i] = i;
        }

    int find(int x) {
        int root = x;
        while (father[root])
            root = father[root];
        int aux;
        while (father[x]) {
            aux = father[x];
            father[x] = root;
            x = aux;
        }
        return root;
    }

    int query(int x) {
        return nxtPos[find(x)];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY)
            return;
        if (height[rootX] < height[rootY])
            father[rootX] = rootY;
        else {
            father[rootY] = rootX;
            nxtPos[rootX] = nxtPos[rootY];
            if (height[rootX] == height[rootY])
                height[rootX]++;
        }
    }
};

int main() {
    int n, a, b, c; fin >> n >> a >> b >> c;
    vector<Query> qry; qry.reserve(n - 1);
    for (int i = 2; i <= n; i++) {
        qry.emplace_back(a, b, c);
        a = 1LL * a * i % n;
        b = 1LL * b * i % n;
        c = 1LL * c * i % n;
    }

    Forest dsu(n);
    vector<int> ans(n);
    for (int i = n - 2; i >= 0; i--)
        for (int x = dsu.query(min(qry[i].a, qry[i].b)); x <= max(qry[i].a, qry[i].b); x = dsu.query(x)) {
            ans[x] = qry[i].c;
            dsu.unite(x, x + 1);
        }
    for (int i = 1; i < n; i++)
        fout << ans[i] << '\n';

    fout.close();
    return 0;
}