Submission #1202025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202025		Nelt	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	0 ms	412 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

vector<int> find_colours(int N,
                         vector<int> X,
                         vector<int> Y)
{
    // 1) build adjacency list & spanning tree via BFS
    vector<vector<int>> adj(N);
    for (int j = 0; j < (int)X.size(); j++)
    {
        adj[X[j]].push_back(Y[j]);
        adj[Y[j]].push_back(X[j]);
    }
    vector<bool> seen(N, false);
    vector<pair<int, int>> tree_edges;
    queue<int> q;
    q.push(0);
    seen[0] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : adj[u])
        {
            if (!seen[v])
            {
                seen[v] = true;
                tree_edges.emplace_back(u, v);
                q.push(v);
            }
        }
    }

    // 2) DSU init
    vector<int> parent(N);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> findp = [&](int u)
    {
        return parent[u] == u ? u : parent[u] = findp(parent[u]);
    };
    auto unite = [&](int u, int v)
    {
        u = findp(u);
        v = findp(v);
        if (u != v)
            parent[v] = u;
    };

    // 3) for each tree edge, test same‑colour
    vector<int> E(N);
    for (auto [u, v] : tree_edges)
    {
        fill(E.begin(), E.end(), N);
        E[u] = E[v] = -1;
        int comps = perform_experiment(E);
        if (comps == 2)
        {
            // u and v share a colour
            unite(u, v);
        }
        // else they differ, leave them separate
    }

    // 4) assign each component an arbitrary label 0..K-1
    vector<int> comp_id(N, -1), G(N);
    int next_label = 0;
    for (int i = 0; i < N; i++)
    {
        int r = findp(i);
        if (comp_id[r] < 0)
            comp_id[r] = next_label++;
        G[i] = comp_id[r];
    }
    return G;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36