Submission #1190405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190405		Swan	Split the Attractions (IOI19_split)	C++20	0 / 100	72 ms	24900 KiB

split

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
 
using namespace std;

const int maxn = 2e5 + 123;
int N;
vector<vector<int> > v;
vector<vector<int> > tree;
bitset<maxn> used;
vector<int> colors;
int sz[maxn];

void dfs0(int u) {
    used[u] = 1;
    sz[u] = 1;

    for (auto a : v[u]) {
        if (used[a]) continue;

        dfs0(a);

        tree[u].push_back(a);
        tree[a].push_back(u);        

        sz[u] += sz[a];
    }
}

void getTree(int root) {
    for (int i = 0; i < N; i++) sz[i] = 0;
    dfs0(root);
}

int getCentroid(int u, int treeSize, int p = -1) {
    for (auto a : tree[u]) {
        if (a == p) continue;
        if (sz[a] > treeSize / 2) {
            return getCentroid(a, treeSize, u);
        }
    }

    return u;
}   

vector<int> vertices;

void getColor(int u, int color, int* sz) {
    if ((*sz) == 0) return;
    used[u] = 1;

    colors[u] = color;
    vertices.push_back(u);

    (*sz)--;    

    for (auto a : v[u]) {
        if (used[a]) continue;
        getColor(a, color, sz);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    v.resize(n + 10);
    tree.resize(n + 10);
    colors.resize(n, 0);

    vector<int> mda = {a, b, c}; sort(mda.begin(), mda.end());
    a = mda[0];
    b = mda[1];
    c = mda[2];

    N = n;
    
    int A = a;
    int B = b;

    for (int i = 0; i < p.size(); i++) {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }

    getTree(0);

    int centroid = getCentroid(0, n);

    tree.clear(); used.reset();
    tree.resize(n + 10);

    getTree(centroid);

    used.reset();


    for (int i = 0; i < tree[centroid].size(); i++) {
        int to = tree[centroid][i];
        if (sz[to] >= a) {
            A = a;
            B = b;
            vertices.clear();

            used[centroid] = 1;
            getColor(to, 1, &A);

            used[centroid] = 0;
            getColor(centroid, 2, &B);

            for (int j = 0; j < n; j++) {
                if (colors[j] == 0) colors[j] = 3;
            }

            return colors;
        }
    }

    used.reset();

    used[centroid] = 1;

    for (int i = 0; i < tree[centroid].size(); i++) {
        int to = tree[centroid][i];
        if (used[to]) continue;

        A = a;
        B = b;
        vertices.clear();

        used[centroid] = 1;
        getColor(to, 1, &A);

        if (!A) {
            used[centroid] = 0;
            getColor(centroid, 2, &B);
            for (int j = 0; j < n; j++) {
                if (colors[j] == 0) colors[j] = 3;
            }

            return colors;
        }

        for (auto a : vertices) colors[a] = 0;
    }

    return colors;
}

/*

void solve() {
    vector<int> res = find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
    
    for (int i = 0; i < res.size(); i++) {
        cout << i << ' ' << res[i] << endl;
    }

    cout << endl;
}

main() {
    ios_base::sync_with_stdio(0);

    solve();
}
    
*/

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