Submission #1224954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224954		im2xtreme	Split the Attractions (IOI19_split)	C++20	Compilation error	0 ms	0 KiB

split

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "split.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>> adj(n);
    for (int i = 0; i < p.size(); ++i) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }

    vector<bool> visited(n, false);
    vector<vector<int>> components;

    // Step 1: Get connected components
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            vector<int> comp;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                comp.push_back(u);
                for (int v : adj[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            components.push_back(comp);
        }
    }

    // If only 1 component, then the graph is fully connected
    // Try to assign sets greedily
    vector<int> result(n, 0);
    vector<int> labels = {1, 2, 3}; // A=1, B=2, C=3
    vector<int> sizes = {a, b, c};
    vector<vector<int>> sets(3);

    // Greedily assign nodes
    int compIndex = 0;
    for (int l = 0; l < 3; ++l) {
        int remaining = sizes[l];
        while (compIndex < components.size() && remaining >= components[compIndex].size()) {
            for (int node : components[compIndex]) {
                sets[l].push_back(node);
            }
            remaining -= components[compIndex].size();
            compIndex++;
        }
        // If partially fill a component
        if (remaining > 0 && compIndex < components.size()) {
            for (int i = 0; i < components[compIndex].size() && remaining > 0; ++i) {
                sets[l].push_back(components[compIndex][i]);
                components[compIndex][i] = -1; // mark as used
                remaining--;
            }
        }
    }

    // Assign results
    int connected = 0;
    for (int i = 0; i < 3; ++i) {
        for (int node : sets[i]) {
            result[node] = i + 1;
        }
        // check if connected
        if (sets[i].size() > 1) connected++;
    }

    if (connected >= 2) return result;
    return vector<int>(n, 0); // no valid partition
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsvbpG5.o: in function `main':
grader.cpp:(.text.startup+0x277): undefined reference to `find_split(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status