제출 #1364135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364135		kahoul	Carnival (EGOI23_carnival)	C++20	40 / 100	72 ms	16080 KiB

Main

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

const int maxn = 1010;
vector<int> rel[maxn];
set<int> disapprove[maxn];

vector<bool> visited (maxn, 0);
vector<int> grau(maxn, 0);

int n;

vector<int> ans;

void dfs (int u) {
    ans.push_back(u);
    visited[u] = 1;

    int min_v = -1;

    for (auto v : rel[u]) {
        if (visited[v]) continue;
        if (min_v == -1 || grau[min_v] > grau[v]) min_v = v;
    }

    if (min_v != -1) dfs(min_v);
}

int main () {
    cin >> n;

    for (int i = 1; i < n; i++) {
        vector<int> vec (i);
        for (int j = 0; j < i; j++) cin >> vec[j];
        for (int j = i - 1; j > (i - 1) / 2; j--) disapprove[i].insert(vec[j]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (disapprove[j].count(i) || disapprove[i].count(j)) continue;
            rel[j].push_back(i);
            rel[i].push_back(j);
            grau[i]++;
            grau[j]++;
        }
    }

    for (int i = 0; i < n; i++) {
        rel[n].push_back(i);
        rel[i].push_back(n);
        grau[n]++;
        grau[i]++;
    }

    dfs(n);

    //assert((ans.size() == n + 1));
    for (auto v : ans) if (v != n) cout << v << ' ';
    cout << '\n';
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 11 / 11
• 서브태스크 2: 0 / 23
• 서브태스크 3: 29 / 29
• 서브태스크 4: 0 / 37