Submission #1354501

#TimeUsernameProblemLanguageResultExecution timeMemory
1354501sallyCarnival (EGOI23_carnival)C++20
40 / 100
1095 ms4496 KiB
#include<iostream>
#include<vector>
#include<cstring>
#include<deque>
#include<bits/stdc++.h>
#define rep(i, x) for(int i=0; i<x; i++)
using namespace std;
const int mx = 1005;
bool ok[mx][mx];
vector<int> cnt(mx, 0);
vector<vector<int>> g(mx);
vector<bool> vis(mx, false);
bool got = false;
vector<int> ans;
int N;
void dfs(int now, int pre, int D) {
    if(D==N) {
        for(int i:ans) cout<<i<<' ';
        got = true;
        return;
    }
    for(int i:g[now]) {
        if(got) return;
        if(i == pre) continue;
        if(vis[i]) continue;
        ans.push_back(i);
        vis[i] = true;
        dfs(i, now, D+1);
        vis[i] = false;
        ans.pop_back();
    }
}
int main() {
    cin>>N;
    memset(ok, true, sizeof(ok));
    for(int i=1; i<N; i++) {
        ok[i][i] = false;
        for(int j=i; j>=1; j--) {
            int c;
            cin>>c;
            if(j<=i/2) {
                ok[i][c] = false;
                ok[c][i] = false;
            }
        }
    }
    int start, stN = 1000000;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(ok[i][j]) g[i].push_back(j);
        }
        if(stN>g[i].size()) {
            stN = g[i].size();
            start = i;
        }
    }
    vis[start] = true;
    ans.push_back(start);
    dfs(start, -1, 1);
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...