Submission #1368096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368096		stanirina	Longest Trip (IOI23_longesttrip)	C++20	Compilation error	0 ms	0 KiB

longesttrip

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

using namespace std;

int n;
vector<bool> vis;

int nadji (const vector<int> & c,const vector<int>& v){
	int sz=v.size();
	if(sz==0)return -1;
	if(!are_conected(c,v))return -1;
	int l=0;
	int r=sz-1;
	vector<int> pom;
	while(l<r){
		int mid=l+(r-l)/2;
		pom.clear();
		for(int i=l;i<=mid;i++)pom.push_back(v[i]);
		if(are_conected(c,pom)r=mid;
		else l=mid+1;
	}
	return v[l];
}

vector<int> longest_trip(int N, int D)
{
	n=N;
	vector<int> s1;
	vector<int> s2;
	s1.push_back(0);
	for(int i=1;i<n;i++){
		bool con=are_conected({0},{i});
		if(con)s1.push_back(i);
		else s2.push_back(i);
	}
	if(s2.size()!=0 && !are_conected(s1,s2)){
		if(s2.size()>s1.size())return s2;
		return s1;
	}
	
	int c1=0;
	int c2=s1[1];
	vis.assign(n,false);
	vis[0]=true;
	vis[c2]=true;
	bool promena=false;
	deque<int> dq;
	dq.push_back(c1);
	dq.push_back(c2);
	vector<int> pom;
	while(true){
		pom.clear();
		for(int i=0;i<n;i++){
			if(!vis[i])pom.push_back(i);
		}
		if(!promena){
			int x=nadji({dq.back()},pom);
			if(x==-1)promena=true;
			else{
				dq.push_back(x);
				vis[x]=true;
			}
		}
		if(promena){
			int x=nadji({dq.front()},pom);
			if(x==-1)break;
			dq.push_front(x);
			vis[x]=true;
		}
	}
	
	pom.clear();
	for(int i=0;i<n;i++)if(!vis[i])pom.push_back(i);
	vector<int> v;
	while(dq.size()!=0){
		v.push_back(dq.back());
		dq.pop_back();
	}
	if(pom.size()==0)return v;
	int poc=-1;
	int kraj=-1;
	poc=nadji(pom,v);
	kraj=nadji({poc},pom);
	int pos=-1;
	vector<int> ans;
	for(int i=0;i<v.size();i++)if(v[i]==poc)pos=i;
	for(int i=0;i<v.size();i++)ans.push_back(v[(pos+i+1)%(v.size())]);
	ans.push_back(kraj);
	for(int i=0;i<pom.size();i++)if(pom[i]!=kraj)ans.push_back(pom[i]);
	return ans;
}

Compilation message (stderr)

longesttrip.cpp: In function 'int nadji(const std::vector<int>&, const std::vector<int>&)':
longesttrip.cpp:12:13: error: 'are_conected' was not declared in this scope; did you mean 'are_connected'?
   12 |         if(!are_conected(c,v))return -1;
      |             ^~~~~~~~~~~~
      |             are_connected
longesttrip.cpp:20:20: error: 'are_conected' was not declared in this scope; did you mean 'are_connected'?
   20 |                 if(are_conected(c,pom)r=mid;
      |                    ^~~~~~~~~~~~
      |                    are_connected
longesttrip.cpp:21:17: error: expected primary-expression before 'else'
   21 |                 else l=mid+1;
      |                 ^~~~
longesttrip.cpp:20:45: error: expected ')' before 'else'
   20 |                 if(are_conected(c,pom)r=mid;
      |                   ~                         ^
      |                                             )
   21 |                 else l=mid+1;
      |                 ~~~~                         
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:33:26: error: 'are_conected' was not declared in this scope; did you mean 'are_connected'?
   33 |                 bool con=are_conected({0},{i});
      |                          ^~~~~~~~~~~~
      |                          are_connected
longesttrip.cpp:37:29: error: 'are_conected' was not declared in this scope; did you mean 'are_connected'?
   37 |         if(s2.size()!=0 && !are_conected(s1,s2)){
      |                             ^~~~~~~~~~~~
      |                             are_connected