Submission #523151

#	Time	Username	Problem	Language	Result	Execution time	Memory
523151		qwerasdfzxcl	Split the Attractions (IOI19_split)	C++14	0 / 100	1 ms	284 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, a, b, c, sz[100100], par[100100];

void dfs(int s, int &cnt, int no, const vector<vector<int>> &adj, int num, vector<int> &ret){
    if (!cnt) return;
    --cnt;
    ret[s] = num;
    if (no==-1) sz[s] = 1;

    for (auto &v:adj[s]) if (v!=no && v!=par[s]){
        if (no==-1) par[v] = s;
        dfs(v, cnt, no, adj, num, ret);
        if (no==-1) sz[s] += sz[v];
    }
}

vector<int> solve_tree(const vector<vector<int>> &adj){
    //printf("n = %d\n", n);
    vector<int> ret(n);
    int N = n;
    dfs(0, N, -1, adj, 3, ret);
    for (int i=1;i<n;i++){
        //printf("%d: %d\n", i, sz[i]);
        int x = sz[i], y = n - sz[i];
        if (a<=x && b<=y){
            dfs(i, a, par[i], adj, 1, ret);
            dfs(par[i], b, i, adj, 2, ret);
            return ret;
        }
        if (a<=y && b<=x){
            dfs(par[i], a, i, adj, 1, ret);
            dfs(i, b, par[i], adj, 2, ret);
            return ret;
        }
    }
    fill(ret.begin(), ret.end(), 0);
    return ret;
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	n = N;
	vector<int> tmp = {A, B, C};
	sort(tmp.begin(), tmp.end());
	a = tmp[0], b = tmp[1], c = tmp[2];

	vector<vector<int>> adj0(N, vector<int>());
	for (int i=0;i<(int)p.size();i++){
        adj0[p[i]].push_back(q[i]);
        adj0[q[i]].push_back(p[i]);
	}
	return solve_tree(adj0);
}

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