제출 #1202091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202091		Nelt	Sphinx's Riddle (IOI24_sphinx)	C++20	50 / 100	524 ms	988 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct Dsu
{
    ll n, ans;
    vector<ll> dsu;
    Dsu(ll sz = 1)
    {
        n = sz;
        ans = n;
        dsu.resize(n + 1, -1);
        init();
    }
    void init()
    {
        for (ll i = 1; i <= n; i++)
            dsu[i] = -1;
    }
    bool Union(ll x, ll y)
    {
        x = repr(x), y = repr(y);
        if (x == y)
            return false;
        if (dsu[x] < dsu[y])
            swap(x, y);
        ans--;
        dsu[y] += dsu[x];
        dsu[x] = y;
        return true;
    }
    ll repr(ll x)
    {
        if (dsu[x] < 0)
            return x;
        return dsu[x] = repr(dsu[x]);
    }
    ll query()
    {
        return ans;
    }
    ll size(ll x)
    {
        return -dsu[repr(x)];
    }
};
const ll N = 255;
bool g[N][N];
bool used[N];
vector<int> send;
ll n;
void dfs(ll v)
{
    used[v] = 1;
    for (ll to = 0; to < n; to++)
        if (g[v][to] and !used[to] and send[to] == n)
            dfs(to);
}
ll compo()
{
    for (ll i = 0; i < n; i++)
        used[i] = 0;
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        if (send[i] == n and !used[i])
            ans++, dfs(i);
    return ans;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
    n = N;
    for (ll i = 0; i < X.size(); i++)
        g[X[i]][Y[i]] = g[Y[i]][X[i]] = 1;
    Dsu dsu(n);
    for (ll i = 0; i < n; i++)
    {
        vector<ll> adj;
        {
            set<ll> s;
            for (ll j = 0; j < i; j++)
                if (g[i][j] and !s.count(dsu.repr(j)))
                    adj.push_back(j), s.insert(dsu.repr(j));
        }
        for (ll ptr = 0; ptr < adj.size();)
        {
            ll l = ptr, r = adj.size() - 1, last = adj.size();
            while (l <= r)
            {
                ll mid = (l + r) >> 1;
                send = vector<int>(n, n);
                for (ll i = 0; i <= mid; i++)
                    send[adj[i]] = -1;
                send[i] = -1;
                ll tot = compo() + 1;
                for (ll j = 0; j < n; j++)
                    if (dsu.repr(j) != dsu.repr(i) and send[j] == -1)
                        tot++;
                ll x = perform_experiment(send);
                if (tot != x)
                    r = mid - 1, last = mid;
                else
                    l = mid + 1;
            }
            if (last != adj.size())
                dsu.Union(i, adj[last]);
            ptr = last + 1;
        }
    }
    vector<int> ans(n);
    for (ll i = 0; i < n; i++) ans[i] = dsu.repr(i);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 18 / 36