Submission #1125234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125234		StefanSebez	Thousands Islands (IOI22_islands)	C++20	31 / 100	109 ms	17396 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];int par[N];
//vector<int>ans;bool imares;
int nekicvor=-1;
void DFS(int u){
	was[u]=true;
	if(E[u].size()>=3||(u==0&&E[u].size()>=2)) {nekicvor=u;return;}
	for(auto i:E[u]){
		if(!was[V[i]]) par[V[i]]=u,DFS(V[i]);
	}
	/*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){
		map<pair<int,int>,int>mapa;
		for(int i=0;i<m;i++){
			E[U[i]].pb(i);
			mapa[{U[i],V[i]}]=i;
		}
		DFS(0);
		if(nekicvor==-1) return false;
		vector<int>res,temp;
		int u=nekicvor;
		//printf("%i\n",nekicvor);
		while(u!=0) temp.pb(u),u=par[u];
		temp.pb(0);
		//for(auto i:temp) printf("%i ",i);printf("\n");
		for(int i=temp.size()-1;i>0;i--) res.pb(mapa[{temp[i],temp[i-1]}]);
        u=nekicvor;
        int ct=0,ind[4];
        for(auto i:E[u]){
			if(ct>1) break;
			if(V[i]==par[u]) continue;
			ind[2*ct]=i;
			if(i%2==0) ind[2*ct+1]=i+1;
			else ind[2*ct+1]=i-1;
			ct++;
        }
        res.pb(ind[0]),res.pb(ind[1]);
		res.pb(ind[2]),res.pb(ind[3]);
		res.pb(ind[1]),res.pb(ind[0]);
		res.pb(ind[3]),res.pb(ind[2]);
		for(int i=1;i<temp.size();i++) res.pb(mapa[{temp[i],temp[i-1]}]);
		return res;
	}
	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: 21 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45