Submission #1352581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352581		mariza	Boardgames (CEOI25_boardgames)	C++20	21 / 100	2095 ms	8696 KiB

boardgames

#include "boardgames.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e5;

struct DSU{
    ll p[N], c;

    void init(ll n){
        for(ll i=0; i<n; i++){
            p[i]=i;
        }
        c=n;
    }

    ll find(ll u){
        if(p[u]==u) return u;
        else return p[u]=find(p[u]);
    }

    void merge(ll u, ll v){
        u=find(u);
        v=find(v);
        if(u!=v){
            p[u]=v;
            c--;
        }
    }
};

vector<int> partition_players(int n, int m, vector<int> x, vector<int> y){
    vector<ll> g[n];
    for(ll i=0; i<m; i++){
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }

    ll i=0;
    vector<int> ans;
    while(i<n){
        ll k=0;
        DSU dsu;
        dsu.init(n);

        for(ll j=i; j<n; j++){
            for(auto nxt:g[j]){
                if(i<=nxt && nxt<=j){
                    dsu.merge(nxt,j);
                    // cout<<nxt<<"-"<<j<<endl;
                }
            }
            // cout<<i<<" "<<j<<": "<<dsu.c<<", "<<i+n-j<<endl;
            if(dsu.c==i+n-j) k=j-i+1;
        }
        ans.push_back(k);
        i+=k;
    }
    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