Submission #1229222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229222		Gray	Split the Attractions (IOI19_split)	C++20	11 / 100	2095 ms	12612 KiB

split

#include "split.h"
#include <algorithm>
#include<bits/stdc++.h>
#include <random>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;

vector<vector<int>> A;
ll n;
vector<int> ass;

void dfs(ll u, ll &cnt, ll wr, ll des){
    ass[u]=wr; cnt++;
    if (cnt==des) return;
    for (auto v:A[u]){
        if (ass[v]) continue;
        dfs(v, cnt, wr, des);
        if (cnt==des) return;
    }
}

bool check(ll r, ll a, ll b, ll c){
    ass.assign(n, 0); queue<ll> proc;
    proc.push(r); ass[r]=1; ll cnt=1;
    while (cnt<a and !proc.empty()){
        auto cur = proc.front(); proc.pop();
        for (auto v:A[cur]){
            if (ass[v]==0){
                ass[v]=1; proc.push(v); cnt++;
            }
            if (cnt==a) break;
        }
    }
    for (ll i=0; i<n; i++){
        if (!ass[i]){
            cnt=0; dfs(i, cnt, 2, b);
            if (cnt==b) return 1;
            else return 0;
        }
    }
    return 0;
}

vector<int> find_split(int N, int ca, int cb, int cc, vector<int> p, vector<int> q) {
    vector<pair<int, int>> e(p.size());
    for (ll i=0; i<(ll)p.size(); i++) e[i] = {p[i], q[i]};
    shuffle(e.begin(), e.end(), mt19937(time(0)));
    n=N; A.resize(n);
    for (ll i=0; i<(ll)p.size(); i++){
        A[e[i].ff].push_back(e[i].ss);
        A[e[i].ss].push_back(e[i].ff);
    }
    vector<ll> a = {ca, cb, cc};
    vector<ll> perm = {0, 1, 2};
    bool ffound=0;
    do{
        bool found=0;
        for (ll i=0; i<n; i++){
            if (check(i, a[perm[0]], a[perm[1]], a[perm[2]])){
                found=1; break;
            }
        }
        if (found) {ffound=1; break;}
    }while (next_permutation(perm.begin(), perm.end()));
    if (ffound){
        for (ll i=0; i<n; i++){
            if (ass[i]==1) ass[i]=perm[0]+1;
            else if (ass[i]==2) ass[i]=perm[1]+1;
            else ass[i]=perm[2]+1;
        }
        return ass;
    }else{
        return vector<int>(n, 0);
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36