Submission #631864

#	Time	Username	Problem	Language	Result	Execution time	Memory
631864		jhnah917	Travelling Salesperson (CCO20_day2problem1)	C++14	25 / 25	560 ms	36140 KiB

Main

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

int N, A[2020][2020];

void Solve(int src){
    list<int> res;
    function<void(int)> add = [&res](int v){
        if(res.size() <= 1){ res.push_back(v); return; }
        int a = *res.begin(), b = *res.rbegin();
        if(A[v][a] == 0) res.push_front(v);
        else if(A[v][b] == 1) res.push_back(v);
        else if(A[a][b] == 0) res.pop_back(), res.push_front(b), res.push_front(v);
        else res.pop_front(), res.push_back(a), res.push_back(v);
    };

    for(int i=1; i<=N; i++) if(i != src) add(i);
    add(src);
    if(*res.begin() != src) res.reverse();

    cout << N << "\n";
    for(auto i : res) cout << i << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=2; i<=N; i++) for(int j=1; j<i; j++) { char c; cin >> c; A[i][j] = A[j][i] = c == 'B'; }
    for(int i=1; i<=N; i++) Solve(i);
}

• Subtask 1: 25 / 25