제출 #614093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614093		2fat2code	Split the Attractions (IOI19_split)	C++17	40 / 100	128 ms	22992 KiB

split

#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 100005;

int N, M, A, B, C, sz[nmax], centroid, indx1, indx2, indx3;
vector<int> res, nod[nmax], nod_MST[nmax];
bitset<nmax>viz;

void dfs(int s){
    viz[s] = 1; sz[s] = 1;
    for(auto it : nod[s]){
        if(!viz[it]){
            nod_MST[s].push_back(it);
            nod_MST[it].push_back(s);
            dfs(it);
            sz[s] += sz[it];
        }
    }
}

void dfs2(int s){
    viz[s] = 1; sz[s] = 1;
    for(auto it : nod_MST[s]){
        if(!viz[it]){
            dfs2(it);
            sz[s] += sz[it];
        }
    }
}

int findcentroid(int s, int par = 0){
    for(auto it : nod_MST[s]){
        if(it != par && sz[it] > (N / 2)){
            return findcentroid(it, s);
        }
    }
    return s;
}

void dfs_vanilla(int s, int par, int cock){
    if(A == 0) return;
    else{
        res[s - 1] = cock;
        A--;
        for(auto it : nod_MST[s]){
            if(it != par && !res[it - 1]) dfs_vanilla(it, s, cock);
        }
    }
}

void construct(int it){
    dfs_vanilla(it, centroid, indx1);
    A = B;
    dfs_vanilla(centroid, 0, indx2);
    for(int i=0;i<N;i++){
        if(!res[i]){
            res[i] = indx3;
        }
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n; M = p.size();
	for(auto &it : p){
        ++it;
	}
	for(auto &it : q){
        ++it;
	}
	vector<pair<int,int>>tz; tz.push_back({a, 1}); tz.push_back({b, 2}); tz.push_back({c, 3});
	sort(all(tz));
	A = tz[0].fr; B = tz[1].fr; C = tz[2].fr;
	indx1 = tz[0].sc, indx2 = tz[1].sc, indx3 = tz[2].sc;
	res.resize(N);
	for(int i=0;i<M;i++){
        nod[p[i]].push_back(q[i]);
        nod[q[i]].push_back(p[i]);
	}
	dfs(1);
	centroid = findcentroid(1);
	viz.reset();
	for(int i=1;i<=n;i++) sz[i] = 0;
	dfs2(centroid);
	for(auto it : nod_MST[centroid]){
        if(sz[it] >= A){
            construct(it);
            return res;
        }
	}
	return res;
}

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