Submission #1063718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063718		aaaaaarroz	Split the Attractions (IOI19_split)	C++17	0 / 100	0 ms	348 KiB

split

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

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    vector<vector<int>> graph(n);
    for (int i = 0; i < q.size(); i++) {
        graph[p[i]].push_back(q[i]);
        graph[q[i]].push_back(p[i]);
    }

    vector<int> ans(n, 0);
    vector<int> component(n, -1);
    vector<int> size;
    
    function<void(int, int)> dfs = [&](int u, int comp_id) {
        component[u] = comp_id;
        size[comp_id]++;
        for (int v : graph[u]) {
            if (component[v] == -1) {
                dfs(v, comp_id);
            }
        }
    };
    
    int comp_count = 0;
    for (int i = 0; i < n; i++) {
        if (component[i] == -1) {
            size.push_back(0);
            dfs(i, comp_count++);
        }
    }

    vector<int> order(comp_count);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) {
        return size[x] > size[y];
    });
    
    if (size[order[0]] >= b + c) {
        int remaining = b + c;
        queue<int> q;
        q.push(-1);
        for (int i = 0; i < n; i++) {
            if (component[i] == order[0]) {
                if (remaining > c) {
                    ans[i] = 2;
                    remaining--;
                } else {
                    ans[i] = 3;
                }
            }
        }
        if (remaining != 0) {
            return vector<int>(n, 0);
        }
    } else {
        int remaining_b = b, remaining_c = c;
        for (int id : order) {
            if (size[id] <= remaining_b && remaining_b > 0) {
                for (int i = 0; i < n; i++) {
                    if (component[i] == id) {
                        ans[i] = 2;
                        remaining_b--;
                    }
                }
            } else {
                for (int i = 0; i < n; i++) {
                    if (component[i] == id && remaining_c > 0) {
                        ans[i] = 3;
                        remaining_c--;
                    }
                }
            }
        }
        if (remaining_b != 0 || remaining_c != 0) {
            return vector<int>(n, 0);
        }
    }

    int remaining_a = a;
    for (int i = 0; i < n; i++) {
        if (ans[i] == 0 && remaining_a > 0) {
            ans[i] = 1;
            remaining_a--;
        }
    }

    if (remaining_a != 0) {
        return vector<int>(n, 0);
    }

    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~

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