Submission #1233330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233330		MuhammadSaram	Longest Trip (IOI23_longesttrip)	C++20	5 / 100	884 ms	1588 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

const int M = 256;

vector<int> nei[M];

int find(vector<int> v,vector<int> v1)
{
	map<int,int> ind;
	for (int i=0;i<v1.size();i++) ind[v1[i]]=i;
	int ans=v1.size()-1;
	for (int u:v)
		for (int i:nei[u])
			if (ind.count(i))
				ans=min(ans,ind[i]);
	return ans;
}

vector<int> cc;
bool vis[M];

void dfs(int u)
{
	vis[u]=1;cc.push_back(u);
	for (int i:nei[u])
		if (!vis[i]) dfs(i);
}

vector<int> longest_trip(int n, int D)
{
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
			if (are_connected({i},{j}))
				nei[i].push_back(j),nei[j].push_back(i);
	dfs(0);
	if (cc.size()<n)
	{
		if (cc.size()*2>=n)
			return cc;
		cc.clear();
		for (int i=0;i<n;i++) 
			if (!vis[i]) cc.push_back(i);
		return cc;
	}
	for (int i=1;i<n;i++) vis[i]=0;
	vector<int> cur={0};
	while (cur.size()<n)
	{
		vector<int> v;
		for (int i=0;i<n;i++)
			if (!vis[i])
				v.push_back(i);
		int x=v[find(cur,v)];
		vis[x]=1;
		int a=find({x},cur);
		reverse(cur.begin(),cur.end());
		int b=find({x},cur);
		if (a<b)
		{
			reverse(cur.begin(),cur.end());
			b=a;
		}
		vector<int> nw={x};
		for (int i=b;i<cur.size();i++)
			nw.push_back(cur[i]);
		for (int i=0;i<b;i++)
			nw.push_back(cur[i]);
		cur=nw;
	}
	return cur;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60