Submission #267069

#	Time	Username	Problem	Language	Result	Execution time	Memory
267069		ChrisT	Travelling Salesperson (CCO20_day2problem1)	C++17	25 / 25	1422 ms	24612 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define all(x) (x).begin(),(x).end()
const int MN = 2e3 + 5;
bool adj[MN][MN];
int main () { //REEEEEE IM SO STUPID
	int n;
	scanf ("%d",&n);
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			char c; scanf (" %c",&c); adj[i][j] = adj[j][i] = c == 'R';
		}
	}
	if (n == 2) return !printf ("2\n1 2\n2\n2 1\n");
	if (n == 3) return !printf ("3\n1 2 3\n3\n2 1 3\n3\n3 1 2\n");
	for (int st = 1; st <= n; st++) { //idk just go in some order :tm:
		int ed = -1;
		vector<vector<int>> conn(n+1);
		for (int i = 1; i <= n; i++) if (i != st) {
			if (~ed) {
				if (conn[ed].empty()) {
					conn[ed].push_back(i); conn[i].push_back(ed);
					continue;
				}
				if (conn[ed].size() == 1) {
					int other = conn[ed][0];
					conn[ed].push_back(i); conn[i].push_back(ed);
					conn[other].push_back(i); conn[i].push_back(other);
					if (adj[i][ed] != adj[i][other]) ed = i;
					continue;
				}
				int del = -1;
				for (int j : conn[ed]) if (adj[j][ed] != adj[i][ed]) {
					del = j;
					break;
				}
				if (del == -1) del = conn[ed][0];
				conn[ed].erase(find(all(conn[ed]),del));
				conn[del].erase(find(all(conn[del]),ed));
				conn[ed].push_back(i); conn[i].push_back(ed);
				conn[del].push_back(i); conn[i].push_back(del);
				if (adj[i][del] == adj[i][ed]) ed = del;
				else ed = i;
			} else ed = i;
		}
		vector<int> path = {st,ed};
		int cur = adj[ed][conn[ed][0]] == adj[st][ed] ? conn[ed][0] : conn[ed][1], lst = ed;
		while (cur != ed) {
			path.push_back(cur); int nxt = -1;
			for (int i : conn[cur]) if (i != lst) nxt = i;
			lst = cur;
			cur = nxt;
		} 
		printf ("%lu\n",path.size());
		for (int i : path) printf ("%d ",i);
		printf ("\n");
		
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  scanf ("%d",&n);
      |  ~~~~~~^~~~~~~~~
Main.cpp:13:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |    char c; scanf (" %c",&c); adj[i][j] = adj[j][i] = c == 'R';
      |            ~~~~~~^~~~~~~~~~

• Subtask 1: 25 / 25