Submission #1352237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352237		Alex1298	Boardgames (CEOI25_boardgames)	C++20	0 / 100	2094 ms	7772 KiB

boardgames

#include <iostream>
#include <vector>

using namespace std;

int n;
int cnt;
vector<int> v[100005];
int dp[100005];
int tata[100005];
int dim[100005];
int last[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 unire(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return;
    }

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

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

vector<int> partition_players(int N, int M, std::vector<int> X,std::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]);
    }

    dp[0] = 0;
    for(int i = 1; i<=n; i++)
    {
        dp[i] = INF;

        for(int j = 1; j<=i; j++)
        {
            tata[j] = j;
            dim[j] = 1;
        }

        cnt = 0;
        for(int j = i; j>=1; j--)
        {
            cnt++;
            for(auto it: v[j])
            {
                if(it > j && it <= i)
                {
                    unire(j, it);
                }
            }

            if(cnt == 1)
            {
                if(dp[j - 1] + 1 < dp[i])
                {
                    dp[i] = dp[j - 1] + 1;
                    last[i] = (i - j + 1);
                }
            }
        }
    }

    vector<int> ans;
    int cur = n;
    while(cur != 0)
    {
        ans.push_back(last[cur]);
        cur -= last[cur];
    }

    return ans;
}

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