Submission #369308

#	Time	Username	Problem	Language	Result	Execution time	Memory
369308		blue	Travelling Salesperson (CCO20_day2problem1)	C++17	0 / 25	1 ms	492 KiB

Main

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> red[2001], blue[2001];

vector<int> res;
vector<bool> visited(2001, 0);
int visited_count;
int cost = 0;

void dfs(int u, int col, bool p)
{
    if(p) res.push_back(u);
    if(!visited[u])
    {
        visited[u] = 1;
        visited_count++;
    }
    bool flag;
    if(col == 0)
    {
        flag = 0;
        for(int v: red[u])
        {
            if(visited[v]) continue;
            flag = 1;
            dfs(v, col, 1);
            break;
        }
        if(!flag)
        {
            if(!cost)
            {
                cost++;
                dfs(u, !col, 0);
            }
        }
    }
    else
    {
        flag = 0;
        for(int v: blue[u])
        {
            if(visited[v]) continue;
            flag = 1;
            dfs(v, col, 1);
            break;
        }
        if(!flag)
        {
            if(!cost)
            {
                cost++;
                dfs(u, !col, 0);
            }
        }
    }
}

int main()
{
    cin >> N;
    char c;
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j < i; j++)
        {
            cin >> c;
            if(c == 'R')
            {
                red[i].push_back(j);
                red[j].push_back(i);
            }
            else
            {
                blue[i].push_back(j);
                blue[j].push_back(i);
            }
        }
    }

    for(int i = 1; i <= N; i++)
    {
        // cout << "i = " << i << '\n';
        cout << N << '\n';

        visited_count = 0;
        visited = vector<bool>(2001, 0);
        res.clear();
        cost = 0;
        dfs(i, 0, 1);


        if(visited_count == N)
        {
            for(int x: res) cout << x << ' ';
            cout << '\n';
            continue;
        }

        visited_count = 0;
        visited = vector<bool>(2001, 0);
        res.clear();
        cost = 0;
        dfs(i, 1, 1);

        for(int x: res) cout << x << ' ';
        cout << '\n';
    }
}

• Subtask 1: 0 / 25