Cod sursa(job #3167226)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 10 noiembrie 2023 13:23:58
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#define ll long long

using namespace std;

ifstream cin("curcubeu.in");
ofstream cout("curcubeu.out");

const int NMAX = 1e6;

struct Query
{
    int A, B, C;
}queries[NMAX + 1];

int n;
pair<int, int> T[NMAX + 1];
int Next[NMAX + 1];

int GetRoot(int node)
{
    int aux = node;
    while(T[node].first > 0)
        node = T[node].first;

    int root = node;
    node = aux;
    while(node != root)
    {
        aux = T[node].first;
        T[node].first = root;
        node = aux;
    }
    return root;
}

void Join(int x, int y, int C)
{
    int rootX = GetRoot(x);
    int rootY = GetRoot(y);

    if(rootX == rootY)
        return;

    if(-T[rootX].first < -T[rootY].first)
        swap(rootX, rootY);

    T[rootX].first += T[rootY].first;
    T[rootY].first = rootX;
    Next[rootX] = max(Next[rootX], Next[rootY]);
    T[rootX].second = C;
}

int main()
{
    cin >> n >> queries[1].A >> queries[1].B >> queries[1].C;
    for(int i = 2; i <= n - 1; i++)
    {
        queries[i].A = ((ll) queries[i - 1].A * i) % n;
        queries[i].B = ((ll) queries[i - 1].B * i) % n;
        queries[i].C = ((ll) queries[i - 1].C * i) % n;
    }

    for(int i = 1; i <= n - 1; i++)
    {
        T[i] = {-1, 0};
        Next[i] = i + 1;
    }

    for(int i = n - 1; i >= 1; i--)
    {
        int x = min(queries[i].A, queries[i].B);
        int y = max(queries[i].A, queries[i].B);
        int C = queries[i].C;

        while(x <= y && T[GetRoot(x)].second != 0)
            x = Next[GetRoot(x)];

        if(x <= y)
        {
            T[GetRoot(x)].second = C;
            int connectNode = x;
            while(x <= y)
            {
                if(T[GetRoot(x)].second == 0)
                    Join(connectNode, x, C);
                x = Next[GetRoot(x)];
            }
        }
    }

    for(int i = 1; i <= n - 1; i++)
        cout << T[GetRoot(i)].second << '\n';

    return 0;
}