Submission #1357359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357359		Alex1298	Boardgames (CEOI25_boardgames)	C++20	21 / 100	2095 ms	8292 KiB

boardgames

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int cnt;
vector<int> v[100005];
int tata[100005];
int dim[100005];
int INF = (1 << 30);

int rad(int x)
{
    if(x == tata[x])
    {
        return x;
    }

    int r = rad(tata[x]);
    tata[x] = r;
    return r;
}

void uneste(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return;
    }

    if(dim[rx] < dim[ry])
    {
        swap(rx, ry);
    }

    cnt--;
    tata[ry] = rx;
    dim[rx] += dim[ry];
}

vector<int> partition_players(int N, int M, vector<int> X, vector<int> Y)
{
    n = N;

    for(int i = 0; i<M; i++)
    {
        X[i]++;
        Y[i]++;

        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }

    vector<int> ans;
    int st = 1;
    while(st <= n)
    {
        cnt = 0;
        int poz = st;
        for(int i = st; i<=n; i++)
        {
            tata[i] = i;
            dim[i] = 1;
            cnt++;

            for(auto it: v[i])
            {
                if(it >= st && it < i)
                {
                    uneste(it, i);
                }
            }

            if(cnt == 1)
            {
                poz = i;
            }
        }

        ans.push_back(poz - st + 1);
        st = poz + 1;
    }

    return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 15 / 15
• Subtask 6: 0 / 34
• Subtask 7: 0 / 17
• Subtask 8: 0 / 16