제출 #942577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942577		MilosMilutinovic	가장 긴 여행 (IOI23_longesttrip)	C++17	45 / 100	808 ms	1368 KiB

longesttrip

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

#define pb push_back

using namespace std;

bool con[305][305];

vector<int> longest_trip(int n,int d){
	if(d!=1) return {};
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			con[i][j]=con[j][i]=are_connected({i},{j});
		}
	}
	vector<int> chn1(1,0),chn2;
	for(int i=1;i<n;i++){
		if(!chn1.empty()&&!chn2.empty()){
			bool ok1=false,ok2=false;
			for(int v:chn1) ok1=(ok1|con[v][i]);
			for(int v:chn2) ok2=(ok2|con[v][i]);
			if(ok1&&ok2){
				for(int x=0;x<(int)chn1.size();x++){
					if(con[chn1[x]][i]){
						swap(chn1[x],chn1.back());
						break;
					}
				}
				for(int x=0;x<(int)chn2.size();x++){
					if(con[chn2[x]][i]){
						swap(chn2[x],chn2[0]);
						break;
					}
				}
				chn1.pb(i);
				for(int v:chn2) chn1.pb(v);
				chn2.clear();
				continue;
			}
			if(!ok1) chn2.pb(i);
			if(!ok2) chn1.pb(i);
			continue;
		}	
		bool ok=false;
		for(int v:chn1) if(con[i][v]) ok=true;
		if(!ok){
			chn2={i};
			continue;
		}
		if(con[chn1[0]][i]){
			reverse(chn1.begin(),chn1.end());
			chn1.pb(i);
			continue;
		}
		while(!con[chn1.back()][i]){
			int x=chn1.back();
			chn1.pop_back();
			reverse(chn1.begin(),chn1.end());
			chn1.pb(x);
			reverse(chn1.begin(),chn1.end());
		}
		chn1.pb(i);
	}
	return chn1.size()>chn2.size()?chn1:chn2;
}

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