제출 #942585

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

longesttrip

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

#define pb push_back

using namespace std;

bool con[305][305];
vector<int> res,cur;

void dfs(int x){
	cur.pb(x);
	if(cur.size()>res.size()) res=cur;
	for(int y=1;y=300;y++){
		if(con[x][y]){
			dfs(y);
		}
	}
	cur.pop_back();
}

mt19937 mrand(time(0));

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){
		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});
			}
		}
		res={};
		for(int i=0;i<n;i++){
			dfs(i);
		}
		return res;
	}
	vector<int> ord(n);
	iota(ord.begin(),ord.end(),0);
	shuffle(ord.begin(),ord.end(),mrand);
	vector<int> chn1(1,ord.back()),chn2;
	ord.pop_back();
	for(int i:ord){
		if(!chn1.empty()&&!chn2.empty()){
			bool ok1=are_connected({i},chn1),ok2=are_connected({i},chn2);
			if(ok1&&ok2){
				if(are_connected({i},{chn2[0]})) swap(chn1,chn2);
				swap(chn1[0],chn1.back());
				int l=0,r=chn2.size()-1,p=0;
				while(l<=r){
					int mid=(l+r)/2;
					vector<int> qv;
					for(int j=0;j<=mid;j++) qv.pb(chn2[j]);
					if(are_connected({i},qv)) p=mid,r=mid-1;
					else l=mid+1;
				}
				swap(chn2[p],chn2[0]);
				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=are_connected({i},chn1);
		if(!ok){
			chn2={i};
			continue;
		}
		if(are_connected({i},{chn1[0]})){
			reverse(chn1.begin(),chn1.end());
			chn1.pb(i);
			continue;
		}
		int l=0,r=(int)chn1.size()-1,p=0;
		while(l<=r){
			int mid=(l+r)/2;
			vector<int> qv;
			for(int j=mid;j<(int)chn1.size();j++) qv.pb(chn1[j]);
			if(are_connected({i},qv)) p=mid,l=mid+1; 
			else r=mid-1;
		}
		p=chn1[p];
		while(chn1.back()!=p){
			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;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'void dfs(int)':
longesttrip.cpp:14:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   14 |  for(int y=1;y=300;y++){
      |              ~^~~~

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