Submission #638311

#	Time	Username	Problem	Language	Result	Execution time	Memory
638311		jamezzz	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	101 ms	18412 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 100005
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front

vector<int> AL[maxn];
deque<int> ans;
map<int,int> to[maxn];

bool dfs(int u,int p){
	vector<int> good;
	for(int v:AL[u]){
		if(v==p)continue;
		good.pb(v);
	}
	if(good.size()>=2){
		int a=to[u][good[0]],b=to[good[0]][u],c=to[u][good[1]],d=to[good[1]][u];
		ans.pb(a);ans.pb(b);ans.pb(c);ans.pb(d);
		ans.pb(b);ans.pb(a);ans.pb(d);ans.pb(c);
		return true;
	}
	for(int v:AL[u]){
		if(v==p)continue;
		if(dfs(v,u)){
			ans.pf(to[u][v]),ans.pb(to[u][v]);
			return true;
		}
	}
	return false;
}

variant<bool,vector<int>> find_journey(int N,int M,vector<int> U,vector<int> V){
	for(int i=0;i<M;i+=2){
		AL[U[i]].pb(V[i]);
		AL[V[i]].pb(U[i]);
		to[U[i]][V[i]]=i;
		to[V[i]][U[i]]=i+1;
	}
	if(dfs(0,-1)){
		vector<int> res;
		for(int i:ans)res.pb(i);
		return res;
	}
	return false;
}

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