Submission #1240603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240603		vako_p	Longest Trip (IOI23_longesttrip)	C++20	60 / 100	343 ms	784 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

int n;

vector<int> f(vector<int> vv, vector<vector<bool>> &edge){
	vector<int> x(n + 5, 1);
	for(int i = 0; i < vv.size(); i++){
		for(int j = i + 1; j < vv.size(); j++){
			if(edge[vv[i]][vv[j]]){
				x[i]++;
				x[j]++;
			}
		}
	}
	ll idx = 0,mn = vv.size();
	for(int i = 0; i < vv.size(); i++){
		if(mn > x[i]){
			mn = x[i];
			idx = i;
		}
	}
	if(mn == vv.size()) return vv;
	vector<int> vv1,vv2,vv3;
	for(int i = 0; i < vv.size(); i++){
		if(!edge[vv[i]][vv[idx]]) vv1.pb(vv[i]);
	}
	for(int i = 0; i < vv.size(); i++){
		int ok = 0;
		for(auto it : vv1){
			if(edge[vv[i]][it]) ok = max(ok, 1);
			if(it == vv[i]) ok = 2;
		}
		if(!ok) vv3.pb(vv[i]);
		else if(ok == 1) vv2.pb(vv[i]);
	}
//	cout << "-> "; for(auto it : vv) cout << it << ' '; cout << endl;
//	cout << "-> "; for(auto it : vv1) cout << it << ' '; cout << endl;
//	cout << "-> "; for(auto it : vv2) cout << it << ' '; cout << endl;
//	cout << "-> "; for(auto it : vv3) cout << it << ' '; cout << endl;
	if(vv2.empty()){
		if(vv1.size() > vv3.size()) return vv1;
		return vv3;
	}	
	vector<int> ans = f(vv2, edge);
	ll num = vv[idx];
	vector<int> v;
	if(ans.size() != vv2.size()){
		for(auto it : vv3) if(it != num) vv2.pb(it);
		ans = f(vv2, edge);
		if(ans.size() != vv2.size()){
			vector<bool> vis(n + 5, false);
			for(auto it : ans){
				v.pb(it);
				vis[it] = true;
			}
			v.pb(num);
			for(auto it : vv2){
				if(!vis[it]) v.pb(it);
			}
			for(auto it : vv1) if(edge[it][v[v.size() - 1]]) num = it;
			v.pb(num);
			for(auto it : vv1) if(it != num) v.pb(it);
			return v;
		}	
		v.pb(num);
		for(auto it : ans) v.pb(it);
		for(auto it : vv1) if(edge[it][v[v.size() - 1]]) num = it;
		v.pb(num);
		for(auto it : vv1) if(it != num) v.pb(it);
		return v;
	}
	for(auto it : vv3) if(it != num) v.pb(it);
	v.pb(num);
	for(auto it : ans) v.pb(it);
	for(auto it : vv1) if(edge[it][v[v.size() - 1]]) num = it;
	v.pb(num);
	for(auto it : vv1) if(it != num) v.pb(it);
	return v;
}

std::vector<int> longest_trip(int N, int D){
	n = N;
	vector<vector<bool>> edge(n + 5, vector<bool>(n + 5, false));
	for(int i = 0; i < n; i++){
		edge[i][i] = true;
		for(int j = i + 1; j < n; j++){
			if(!are_connected({i}, {j})) continue;
			edge[i][j] = edge[j][i] = true;
		}
	}
	vector<int> v;
	for(int i = 0; i < n; i++) v.pb(i);
	return f(v, edge);
}

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