Submission #721980

#	Time	Username	Problem	Language	Result	Execution time	Memory
721980		pere_gil	Thousands Islands (IOI22_islands)	C++17	0 / 100	3 ms	2772 KiB

islands

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

#define ii pair<int,int>

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

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

	if((!u && adj[u].size()>=2) || (u && adj[u].size()>=3)){
		piv=u;
		int a=-1,b=-1,c=-1,d=-1;
		for(auto v: adj[u]){
			if(v.first==pa) continue;
			if(a==-1)
				a=v.second.first,b=v.second.second;
			else{
				c=v.second.first,d=v.second.second;
				break;
			}
		}

		res=path;
		for(int i: {a,b,c,d,b,a,d,c}) 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.first);
		dfs(v.first,u);
		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,i+1}});
		adj[v[i]].push_back({u[i],{i+1,i}});
	}

	for(int i=0;i<n;i++){
		printf("%d\n",i);
		for(auto x: adj[i]) printf("     %d: %d %d\n",x.first,x.second.first,x.second.second);
	}

	dfs(0,-1);
	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