Submission #655474

#	Time	Username	Problem	Language	Result	Execution time	Memory
655474		dooompy	Split the Attractions (IOI19_split)	C++17	0 / 100	584 ms	1048576 KiB

split

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

using namespace std;

int n, m;
int par[100005], sz[100005], sztree[100005];
vector<int> graph[100005], tree[100005], inter[100005];
pair<int, int> info[3];

int findset(int i) {
    return (i == par[i] ? i : par[i] = findset(par[i]));
}

bool onion(int a, int b) {
    a = findset(a), b = findset(b);

    if (a == b) return false;

    if (sz[a] < sz[b]) swap(a, b);

    par[b] = a;
    sz[a] += sz[b];
    return true;
}

void dfscent(int node, int par = -1) {
    sztree[node] = 1;
    for (auto nxt : tree[node]) {
        if (nxt == par) continue;
        dfscent(nxt, node);
        sztree[node] += sz[nxt];
    }
}

int centroid(int node, int par = -1) {

    for (auto nxt : tree[node]) {
        if (nxt == par) continue;
        if (sztree[nxt] * 2 > sz[0]) return centroid(nxt, node);
    }

    return node;
}

vector<int> nodes;

void dfs(int node, int par) {
    nodes.push_back(node);
    for (auto nxt : graph[node]) {
        if (nxt == par) continue;

        onion(nxt, node);
        dfs(nxt, node);
    }
}

int state[100005];
bool createseen[100005];

vector<int> ansnodes;

void dfscreate(int node) {
    ansnodes.push_back(node);
    createseen[node] = true;

    for (auto nxt : graph[node]) {
        if (!createseen[nxt] && state[nxt] == state[node]) dfscreate(nxt);
    }
}

vector<int> create() {
    vector<int> ans(n, info[2].second);

    for (auto cur : nodes) {
        state[cur] = 1;
    }

    for (int i = 0; i < n; i++) {
        if (state[i] == 1 && !createseen[i]) {
            ansnodes.clear();
            dfscreate(i);

            for (int j = 0; j < info[0].first; j++) {
                ans[ansnodes[j]] = info[0].second;
            }
        }

        if (state[i] == 0 && !createseen[i]) {
            ansnodes.clear();
            dfscreate(i);

            for (int j = 0; j < info[1].first; j++) {
                ans[ansnodes[j]] = info[1].second;
            }
        }
    }

    return ans;
}

bool seen[100005];

vector<int> across;

void dfsacross(int node) {
    across.push_back(node);
    seen[node] = true;

    for (auto nxt : inter[node]) {
        if (!seen[nxt]) dfsacross(nxt);
    }
}

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

    info[0] = {a, 0};
    info[1] = {b, 1};
    info[2] = {c, 2};

    sort(info, info + 3);

    for (int i = 0; i < n; i++) {
        par[i] = i; sz[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);

        if (onion(p[i], q[i])) {
            tree[p[i]].push_back(q[i]);
            tree[q[i]].push_back(p[i]);
        }
    }

    dfscent(0);
    int cent = centroid(0);

    for (int i = 0; i < n; i++) {
        par[i] = i; sz[i] = 1;
    }

    for (auto nxt : tree[cent]) {
        nodes.clear();
        dfs(nxt, cent);

        if (nodes.size() >= info[0].first) {
            // rest are connected

            return create();
        }
    }

    vector<int> asdf(1000000000000, 0);

    for (int i = 0; i < m; i++) {
        if (p[i] == cent || q[i] == cent) continue;
        int a = findset(p[i]), b = findset(q[i]);

        if (a == b) continue;
        inter[a].push_back(b);
        inter[b].push_back(a);
    }

    for (int i = 0; i < n; i++) {
        if (findset(i) == i && i != c && !seen[i]) {
            across.clear();
            dfsacross(i);

            int ct = 0;
            set<int> used;

            for (auto tre : across) {
                ct += sz[findset(tre)];
                used.insert(tre);

                if (ct >= info[0].first) break;
            }

            if (ct >= info[0].first) {
                nodes.clear();

                for (int j = 0; j < n; j++) {
                    if (used.count(findset(j))) nodes.push_back(j);
                }

                return create();
            }
        }
    }

    return vector<int> (n, 0);


}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:149:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |         if (nodes.size() >= info[0].first) {
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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