Submission #1125230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125230		StefanSebez	Thousands Islands (IOI22_islands)	C++20	17.35 / 100	30 ms	8228 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
vector<int>E[N];
int U[2*N],V[2*N];
bool was[N];
vector<int>ans;bool imares;
void DFS(int u){
	vector<int>nesto;
	for(auto i:E[u]){
		if(!was[i]) nesto.pb(i);
	}
	if(nesto.size()>=2){
		int ind[4];
		ind[0]=nesto[0];
		if(ind[0]%2==0) ind[1]=ind[0]+1;
		else ind[1]=ind[0]-1;
		ind[2]=nesto[1];
		if(ind[2]%2==0) ind[3]=ind[2]+1;
		else ind[3]=ind[2]-1;
		ans.pb(ind[0]),ans.pb(ind[1]);
		ans.pb(ind[2]),ans.pb(ind[3]);
		ans.pb(ind[1]),ans.pb(ind[0]);
		ans.pb(ind[3]),ans.pb(ind[2]);
		imares=true;
		return;
	}
	bool bul=false;
	for(auto i:E[u]){
		if(!was[i]){
			was[i]=true;
			int j=i;
			if(j%2==0) j++;
			else j--;
			was[j]=true;
			ans.pb(i);
			DFS(V[i]);
			ans.pb(j);
			bul=true;
			break;
		}
	}
	if(!bul) ans.pop_back();
}
std::variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U1, std::vector<int> V1) {
	for(int i=0;i<m;i++) U[i]=U1[i],V[i]=V1[i];
	bool subtask3=true;if(m%2==1) subtask3=false;
	for(int i=0;i<m;i++) if(m%2==0&&i%2==0&&(U[i]!=V[i+1]||V[i]!=U[i+1])) subtask3=false;
	if(n==2){
		int deg[n+10]={0};
		vector<int>nesto[n+10];
		for(int i=0;i<m;i++){
			deg[U[i]]++;
			nesto[U[i]].pb(i);
		}
		if(deg[0]<=1||deg[1]<=0) return false;
		return (vector<int>){nesto[0][0],nesto[1][0],nesto[0][1],nesto[0][0],nesto[1][0],nesto[0][1]};
	}
	if(subtask3){
		for(int i=0;i<m;i++) E[U[i]].pb(i);
		DFS(0);
		if(!imares) return false;
		return ans;
	}
	else{
		int ind[10];
		for(int i=0;i<m;i++){
			if(U[i]==0&&V[i]==1) ind[0]=i;
			if(U[i]==1&&V[i]==0) ind[1]=i;
			if(U[i]==0&&V[i]==2) ind[2]=i;
			if(U[i]==2&&V[i]==0) ind[3]=i;
		}
		if(n==2) return false;
		return (vector<int>){ind[0],ind[1],ind[2],ind[3],ind[1],ind[0],ind[3],ind[2]};
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45