Submission #143630

#	Time	Username	Problem	Language	Result	Execution time	Memory
143630		muradeyn	Split the Attractions (IOI19_split)	C++14	0 / 100	134 ms	13688 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxx = 200000;

int N , pos = -1 , par , cent;
int dp[maxx];

vector< pair<int,int> >spl;

vector<int>adj[maxx];

void dfs(int s,int p) {
    dp[s] = 1;
    bool f = true;
    for (int to : adj[s]) {
        if (to == p)continue;
        dfs(to , s);
        if (dp[to] >= spl[0].F) {
            if (pos == -1)pos = to , par = s;
            else if (dp[pos] > dp[to])pos = to , par = s;
        }
        f &= (dp[to] <= N / 2);
        dp[s] += dp[to];
    }
    f &= (N - dp[s] <= N / 2);
    if (f)cent = s;
}

vector<int>res;

int cnt = 0;

void label(int s,int p,int need,int mark) {
    cnt++;
    res[s] = mark;
    if (cnt == need)return;
    for (int to : adj[s]) {
        if (to == p || to == pos)continue;
        label(to , s , need , mark);
        if (cnt == need)return;
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	res.resize(n , 0);
	spl.push_back({a , 1});
	spl.push_back({b , 2});
	spl.push_back({c , 3});
	sort(spl.begin(),spl.end());
	int m = p.size();
	if (n != m + 1)return res;
	for (int i = 0;i<m;i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
	}
	dfs(1 , -1);
	int rt = cent;
	dfs(rt , -1);
	if (pos == -1)return res;
	//if (n - dp[pos] < spl[1].F)return res;
	label(pos , par , spl[0].F , spl[0].S);
	cnt = 0;
	label(rt , -1 , spl[1].F , spl[1].S);
	for (int i = 0;i<n;i++)
        if (res[i] == 0)res[i] = spl[2].S;
    return res;
}

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