Submission #1070109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070109		j_vdd16	Split the Attractions (IOI19_split)	C++17	0 / 100	35 ms	9852 KiB

split

#include "split.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

int n, m;
int a, b, c;
vvi adj;
vi res;

vb vis;
vi subSize;
ii marked;
vector<ii> types;
int dfs(int node, int parent) {
    vis[node] = true;

    int maxSize = 0;
    for (int child : adj[node]) {
        if (vis[child]) continue;

        int childSz = dfs(child, node);
        maxSize = max(maxSize, childSz);

        subSize[node] += childSz;
    }
    subSize[node]++;

    if (maxSize < types[1].first && subSize[node] >= types[1].first && n - subSize[node] >= types[2].first) {
        marked = { node, parent };
    }

    return subSize[node];
}

void partition(int node, int type) {
    vis[node] = true;

    auto& [nodesLeft, value] = types[type];
    if (nodesLeft == 0) {
        type = 3;
        res[node] = 3;
    }
    else {
        nodesLeft--;
        res[node] = value;
    }

    for (int child : adj[node]) {
        if (vis[child]) continue;

        if (node == marked.first) {
            if (child == marked.second) {
                partition(child, 2);
            }
            else {
                partition(child, 1);
            }
        }
        else {
            partition(child, type);
        }
    }
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
    n = _n, m = (int)p.size();
    adj = vvi(n);
    a = _a, b = _b, c = _c;

    loop(i, m) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }

    vis = vb(n);
    subSize = vi(n);
    marked = { -1, -1 };
    types = {{0, 0}, {a, 1}, {b, 2}, {c, 3}};
    sort(all(types));
    dfs(0, -1);

    res = vi(n);
    if (marked == ii{-1, -1}) {
        return res;
    }

    vis = vb(n, false);
    partition(marked.first, 1);
	return res;
}

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