제출 #1203304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203304		Lalic	Split the Attractions (IOI19_split)	C++17	0 / 100	605 ms	1114112 KiB

split

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair

vector<vector<int>> adj;
vector<int> tam, val = {1, 2, 3};

int getSz(int ver, int prev = -1){
    tam[ver] = 1;

    for(auto u : adj[ver]){
	if(u == prev)
	    continue;
	tam[ver] += getSz(u, ver);
    }

    return tam[ver];
}

int getCentroid(int ver, int tot, int prev = -1){
    for(auto u : adj[ver]){
	if(u == prev)
	    continue;

	if(tam[u] >= (tot + 1) / 2)
	    return getCentroid(u, tot, ver);
    }
    return ver;
}

void paint(int ver, vector<int>& qnt, vector<int>& res, int color, int prev = -1){
    res[ver] = color;
    qnt[color]--;

    for(auto u : adj[ver]){
	if(!qnt[color])
	    return;

	if(u == prev)
	    continue;
	paint(u, qnt, res, color, ver);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    adj.resize(n);
    tam.resize(n);
    
    vector<int> qnt = {0, a, b, c};

    if(a > c){
	swap(a, c);
	swap(val[0], val[2]);
    }
    if(b > c){
	swap(b, c);
	swap(val[1], val[2]);
    }
    if(a > b){
	swap(a, b);
	swap(val[0], val[1]);
    }

    for(int i = 0; i < (int)p.size(); i++){
	int a = p[i], b = q[i];
	adj[a].pb(b);
	adj[b].pb(a);
    }

    int centroid = getCentroid(0, getSz(0));
    getSz(centroid);

    vector<int> res(n, val[2]); res[centroid] = val[1]; qnt[val[1]]--;

    bool ok = 0;
    for(auto u : adj[centroid]){
	if(ok){
	    if(!qnt[val[1]])
		break;
	    paint(u, qnt, res, val[1], centroid);
	    continue;
	}

	if(tam[u] >= a){
	    paint(u, qnt, res, val[0], centroid);
	    ok = 1;
	}
	else if(qnt[val[1]])
	    paint(u, qnt, res, val[1]);
    }

    if(!ok)
	for(auto& u : res)
	    u = 0;

    return res;
}

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