Submission #1048056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048056		NotLinux	Split the Attractions (IOI19_split)	C++17	18 / 100	2029 ms	15696 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
const int inf = 1e9 + 7;
const int LIM1 = 1e5 + 7;
int subt[LIM1] , N , A , B , C , vis[LIM1] , past[LIM1];
vector < int > graph[LIM1] , color;
int root = -1;
pair < int , int > pai;
random_device rd;
mt19937 rng(rd());
// shuffle(v.begin() , v.end() , rng);
int rand(int l, int r) {
    return rng() % (r - l + 1) + l;
}
void dfs(int node , int par){
    // cout << "bruh0" << endl;
    subt[node] = 1;
    // cout << "bruh0.1" << endl;
    past[node] = par;
    // cout << "bruh0.2" << endl;
    // cout << "bruh0.3" << endl;
    shuffle(all(graph[node]) , rng);
    // cout << "bruh1" << endl;
    for(auto itr : graph[node]){
        if(subt[itr] == -1){
            dfs(itr , node);
            subt[node] += subt[itr];
        }
    }
    // cout << node << " : " << subt[node] << " , " << par << endl;
    // if(node == 4)cout << "wtf : " << subt[node] << " >= " << C << " , " << N - subt[node] << " >= " << B << endl;
    if(subt[node] >= A and (N - subt[node]) >= B)pai = {1 , 2} , root = node;
    if(subt[node] >= B and (N - subt[node]) >= A)pai = {2 , 1} , root = node;
    if(subt[node] >= A and (N - subt[node]) >= C)pai = {1 , 3} , root = node;
    if(subt[node] >= C and (N - subt[node]) >= A)pai = {3 , 1} , root = node;
    if(subt[node] >= B and (N - subt[node]) >= C)pai = {2 , 3} , root = node;
    if(subt[node] >= C and (N - subt[node]) >= B)pai = {3 , 2} , root = node;
}
int sayac;
void dfs1(int node , int paint){
    if(sayac == 0)return;
    color[node] = paint;
    vis[node] = 1;
    sayac--;
    // cout << "Dfs : " << node << " , " << paint << " , " << past[node] << endl;
    for(auto itr : graph[node]){
        if(vis[itr] == 0 and itr != past[node] and past[itr] == node){
            // cout << node << "->" << itr << endl;
            dfs1(itr , paint);
        }
    }
}
void solve(){
    root = -1;
    // cout << "flag-0"<<endl;
    memset(vis , 0 , sizeof(vis));
    memset(subt , -1 , sizeof(subt));
    // cout << "flag-1"<<endl;
    int real_root = rand(0 , N-1);
    dfs(real_root , -1);
    // cout << "flag-2"<<endl;
    // cout << "root : "<< root << endl;
    // cout << "lower : " << pai.first << endl;
    // cout << "upper : " << pai.second << endl;
    if(root != -1){
        int q[3] = {A , B , C};
        set < int > ste = {1 , 2 , 3};
        ste.erase(ste.find(pai.first));
        ste.erase(ste.find(pai.second));
        color.assign(N , *ste.begin());
        // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
        sayac = q[pai.first - 1];
        dfs1(root , pai.first);
        // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
        sayac = q[pai.second - 1];
        dfs1(real_root , pai.second);
        // cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    N = n , A = a , B = b , C = c;
    for(int i = 0;i<sz(p);i++){
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
    }
    const int BRUH = 750;
    color.assign(N , 0);
    // cout << "flag0" << endl;
    for(int i = 0;i<BRUH;i++){
        // cout << "flag0.1" << endl;
        solve();
        if(color[0] != 0)break;
    }
    // cout << "flag1" << endl;
    return color;
}

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