Submission #721954

#	Time	Username	Problem	Language	Result	Execution time	Memory
721954		pere_gil	Thousands Islands (IOI22_islands)	C++17	0 / 100	1173 ms	1536420 KiB

islands

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

#define ii pair<int,int>

const int MAX_N=1e5+5;
vector<ii> adj[MAX_N];
vector<bool> vis(MAX_N,false);
vector<int> path,res;
int piv=-1;

void dfs(int u){
	if(piv!=-1) return;
	vis[u]=false;

	if(adj[u].size()>=2){
		piv=u;
		int a=adj[u][0].second,b=adj[u][1].second;
		vector<int> aux={a,a+1,b,b+1,a+1,a,b+1,b};
		
		res=path;
		for(int i: aux) res.push_back(i);
		for(int i=path.size()-1;i>=0;i--) res.push_back(path[i]);
		
		return;
	}

	for(auto v: adj[u]){
		if(vis[v.first]) continue;
		path.push_back(v.second);
		dfs(v.first);
		path.pop_back();
	}
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v){
	for(int i=0;i<m;i+=2)
		adj[u[i]].push_back({v[i],i});

	dfs(0);
	if(piv==-1) return false;
	return res;
}

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