Submission #638312

#	Time	Username	Problem	Language	Result	Execution time	Memory
638312		jamezzz	Thousands Islands (IOI22_islands)	C++17	26 / 100	105 ms	22884 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];
map<int,int> to2[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,b,c,d;
		if(good[0]==good[1])a=to[u][good[0]],b=to[good[0]][u],c=to2[u][good[1]],d=to2[good[1]][u];
		else 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){
		AL[U[i]].pb(V[i]);
		if(to[U[i]].find(V[i])!=to[U[i]].end())to2[U[i]][V[i]]=i;
		else to[U[i]][V[i]]=i;
	}
	if(dfs(0,-1)){
		vector<int> res;
		for(int i:ans)res.pb(i);
		return res;
	}
	return false;
}

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