제출 #852293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852293		Wansur	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	12 ms	1948 KiB

longesttrip

#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
 
using namespace std;
typedef long long ll;
 
const int mx=5e2+12;
 
vector<int> g[mx];
int was[mx][mx];
 
bool are_connected(std::vector<int> A, std::vector<int> B);
 
int  ask(int a,int b){
	if(!was[a][b]){
		was[a][b]=was[b][a]=(int)are_connected({a},{b})+1;
	}
	return was[a][b]-1;
}
 
std::vector<int> longest_trip(int n, int d){
	vector<int> ans;
	if(d==3){
		for(int i=0;i<n;i++){
			ans.push_back(i);
		}
		return ans;
	}
	bool used[n+12]={};
	if(d==2){
		deque<int> ans;
		ans.push_back(0);
		for(int i=1;i<n;i++){
			if(are_connected({0},{i})){
				ans.push_back(i);
				used[0]=1;
				used[i]=1;
				break;
			}
		}
		for(int i=1;i<n;i++){
			if(used[i]){
				continue;
			}
			if(are_connected({ans.back()},{i})){
				ans.push_back(i);
			}
			else{
				ans.push_front(i);
			}
		}
		vector<int> v;
		for(int x:ans){
			v.push_back(x);
		}
		return v;
	}
	for(int i=0;i<n;i++){
		g[i].clear();
		for(int j=0;j<n;j++){
			was[i][j]=0;
		}
	}
	srand(time(0));
	vector<int> t;
	for(int i=0;i<n;i++){
		g[i].push_back(i);
		t.push_back(i);
	}
	while(t.size()>2){
		int a=t[0],b=t[1],c=t[2];
		vector<pair<int,int>> d;
		d.push_back({a,b});
		d.push_back({a,c});
		d.push_back({b,c});
		random_shuffle(d.begin(),d.end());
		int v,u;
		if(ask(d[0].f,d[0].s)){
			v=d[0].f,u=d[0].s;
		}
		else if(ask(d[1].f,d[1].s)){
			v=d[1].f,u=d[1].s;
		}
		else{
			v=d[2].f,u=d[2].s;
		}
		reverse(g[v].begin(),g[v].end());
		for(int x:g[u]){
			g[v].push_back(x);
		}
		g[u].clear();
		int x=g[v][0];
		if(x!=v){
			for(int to:g[v]){
				g[x].push_back(to);
			}
			g[v].clear();
		}
		t.clear();
		for(int i=0;i<n;i++){
			if((int)g[i].size()>0){
				t.push_back(i);
			}
		}
	}
	int a=t[0],b=t[1];
	if(are_connected(g[a],g[b])){
		vector<int> ans;
		vector<int> v=g[a],u=g[b];
		if(ask(v[0],u.back())){
			ans=u;
			for(int x:v){
				ans.push_back(x);
			}
			return ans;
		}
		if(ask(v[0],u[0])){
			reverse(u.begin(),u.end());
			ans=u;
			for(int x:v){
				ans.push_back(x);
			}
			return ans;
		}
		if(ask(v.back(),u[0])){
			ans=v;
			for(int x:u){
				ans.push_back(x);
			}
			return ans;
		}
		if(ask(v.back(),u.back())){
			ans=v;
			reverse(u.begin(),u.end());
			for(int x:u){
				ans.push_back(x);
			}
			return ans;
		}
		int pos=-1,pos1=-1;
		for(int l=1,r=v.size();l<=r;){
			int mid=l+r>>1;
			vector<int> t;
			for(int i=0;i<mid;i++){
				t.push_back(v[i]);
			}
			if(are_connected(t,u)){
				pos=mid-1;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		for(int l=1,r=u.size();l<=r;){
			int mid=l+r>>1;
			vector<int> t;
			for(int i=0;i<mid;i++){
				t.push_back(u[i]);
			}
			if(are_connected({v[pos]},t)){
				pos1=mid-1;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		vector<int> x,y;
		for(int i=pos;i<v.size();i++){
			x.push_back(v[i]);
		}
		for(int i=0;i<pos;i++){
			x.push_back(v[i]);
		}
		for(int i=pos1;i<u.size();i++){
			y.push_back(u[i]);
		}
		for(int i=0;i<pos1;i++){
			y.push_back(u[i]);
		}
		reverse(x.begin(),x.end());
		for(int t:x){
			ans.push_back(t);
		}
		for(int t:y){
			ans.push_back(t);
		}
		return ans;
	}
	else{
		if((int)g[a].size()>(int)g[b].size()){
			return g[a];
		}
		else{
			return g[b];
		}
	}
}

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

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:145:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |    int mid=l+r>>1;
      |            ~^~
longesttrip.cpp:159:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |    int mid=l+r>>1;
      |            ~^~
longesttrip.cpp:173:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |   for(int i=pos;i<v.size();i++){
      |                 ~^~~~~~~~~
longesttrip.cpp:179:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   for(int i=pos1;i<u.size();i++){
      |                  ~^~~~~~~~~

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