제출 #1242950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242950		ericl23302	스핑크스 (IOI24_sphinx)	C++20	10 / 100	44 ms	1168 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h> 

using namespace std;

void dfs(int cur, vector<bool> &visited, vector<vector<int>> &adjacency, int erased) {
    visited[cur] = true;
    for (auto &i : adjacency[cur]) {
        if (visited[i] || i == erased) continue;
        dfs(i, visited, adjacency, erased);
    }
}

int countComponents(int erased, int N, vector<vector<int>> &adjacency) {
    vector<bool> visited(N, false);
    int cnt = 1;
    for (int i = 0; i < N; ++i) {
        if (visited[i] || i == erased) continue;
        dfs(i, visited, adjacency, erased);
        ++cnt;
    }
    return cnt;
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
    vector<int> G(N, -1);
    vector<vector<int>> adjacency(N);
    for (int i = 0; i < X.size(); ++i) {
        adjacency[X[i]].push_back(Y[i]);
        adjacency[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < N; ++i) {
        int expected = countComponents(i, N, adjacency);
        for (int colour = 0; colour < N; ++colour) {
            vector<int> E(N, colour);
            E[i] = -1;
            int cur = perform_experiment(E);
            if (cur < expected) {
                G[i] = colour;
                break;
            }
        }
    }

    return G;
}

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