Submission #1048031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048031		NotLinux	Split the Attractions (IOI19_split)	C++17	0 / 100	5 ms	11612 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 , tree[LIM1];
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){
    subt[node] = 1;
    past[node] = par;
    tree[par].push_back(node);
    shuffle(all(graph[node]) , rng);
    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 : tree[node]){
        if(vis[itr] == 0 and itr != past[node]){
            // cout << node << "->" << itr << endl;
            dfs1(itr , paint);
        }
    }
}
void solve(){
    memset(vis , 0 , sizeof(vis));
    memset(subt , -1 , sizeof(subt));
    for(int i = 0;i<N;i++)tree[i].clear();
    dfs(0 , -1);
    // 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.extract(pai.first);
        ste.extract(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(0 , 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 = 5000;
    color.assign(N , 0);
    for(int i = 0;i<BRUH;i++){
        solve();
    }
    return color;
}

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