Submission #260205

#	Time	Username	Problem	Language	Result	Execution time	Memory
260205		dolphingarlic	Split the Attractions (IOI19_split)	C++14	0 / 100	117 ms	11488 KiB

split

#include "split.h"

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> graph[100000];
vector<pair<int, int>> lab;

bool in_a[100000];
int cmp[100000], cmp_sz[100000];
int find(int A) {
    while (A != cmp[A]) A = cmp[A], cmp[A] = cmp[cmp[A]];
    return A;
}
void onion(int A, int B) {
    if (find(A) != find(B)) {
        cmp_sz[find(A)] += cmp_sz[find(B)];
        cmp[find(B)] = find(A);
    }
}

bool possible() {
    queue<int> q;
    q.push(0);
    in_a[0] = true;
    for (int cnt = 1; cnt < lab[0].first;) {
        int curr = q.front();
        q.pop();
        for (int i : graph[curr]) {
            if (!in_a[i] && cnt < lab[0].first) {
                in_a[i] = true;
                q.push(i);
                cnt++;
            }
        }
    }
    iota(cmp, cmp + n, 0);
    fill(cmp_sz, cmp_sz + n, 1);
    for (int i = 0; i < n; i++) if (!in_a[i]) {
        for (int j : graph[i]) if (!in_a[j]) onion(i, j);
    }
    for (int i = 0; i < n; i++) {
        if (!in_a[i] && cmp_sz[find(i)] >= lab[0].first) return true;
    }
    return false;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    n = N;
    lab = {{a, 1}, {b, 2}, {c, 3}};
    sort(lab.begin(), lab.end());
    for (int i = 0; i < p.size(); i++) {
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
    }

    if (!possible()) return vector<int>(n, 0);

    vector<int> ret(n);
    for (int i = 0; i < n; i++) {
        if (i < lab[0].first) ret[i] = lab[0].second;
        else if (i < lab[0].first + lab[1].first) ret[i] = lab[1].second;
        else ret[i] = lab[2].second;
    }
    return ret;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++) {
                     ~~^~~~~~~~~~

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