제출 #1315028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315028		PlayVoltz	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	6 ms	412 KiB

longesttrip

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

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

vector<int> longest_trip(int n, int d){
	if (d==3){
		vector<int> ans;
		for (int i=0; i<n; ++i)ans.pb(i);
		return ans;
	}
	if (d==2){
		deque<int> ans(1, 0);
		int done=1;
		if (are_connected({0}, {1}))ans.pb(1);
		else ans.pb(2), done=2;
		for (int i=1; i<n; ++i)if (i!=done){
			if (are_connected({i}, {ans.back()}))ans.pb(i);
			else ans.push_front(i);
		}
		vector<int> res;
		for (auto a:ans)res.pb(a);
		return res;
	}
	vector<int> ord;
	for (int i=1; i<n; ++i)ord.pb(i);
	mt19937 gen(67);
	shuffle(ord.begin(), ord.end(), gen);
	deque<int> ans(1, 0);
	set<int> s;
	for (int i=1; i<n; ++i)s.insert(i);
	int loop=256, calls=20000;
	while (loop--&&calls&&s.size()>n/2){
		vector<int> temp;
		for (int i:s){
			i=ord[i];
			if (!calls)break;
			--calls;
			if (are_connected({i}, {ans.back()})){
				ans.pb(i);
				temp.pb(i);
				continue;
			}
			if (!calls)break;
			--calls;
			if (are_connected({i}, {ans[0]}))ans.push_front(i), temp.pb(i);
		}
		for (auto a:temp)s.erase(a);
	}
	vector<int> res;
	for (auto a:ans)res.pb(a);
	return res;
}

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