Submission #1024701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024701		shenfe1	Thousands Islands (IOI22_islands)	C++17	6.75 / 100	21 ms	10020 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>

#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define in insert
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()

using namespace std;

const int MAX=2e5+10;

vector<pii> g[MAX];
int use[MAX];
int pr[MAX];
int d[MAX];
int cycle;

void dfs(int v,int p=-1){
	pr[v]=p;
	use[v]=1;
	for(auto to:g[v]){
		if(pr[v]!=-1&&to.S==(pr[v]%2==0?pr[v]+1:pr[v]-1))continue;
		if(!use[to.S])continue;
		d[to.F]=d[v]+1;
		dfs(to.F,to.S);
	}
	if(sz(g[v])-(v>0)>=2){
		cycle=v;
	}
}

int rev(int x){
	return (x%2==0?x+1:x-1);
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,vector<int> V){
	// return true;
	cycle=-1;
	for(int i=0;i<M;i++){
		g[U[i]].pb({V[i],i});
	}
	if(N==2){
		if(sz(g[0])>=2&&sz(g[1])>=1){
			vector<int> vec={g[0][0].S,g[1][0].S,g[0][1].S,g[0][0].S,g[1][0].S,g[0][1].S};
			return vec;
		}return false;
	}

	for(int i=0;i<N;i++){
		if(sz(g[i])-(i>0)>=2){
			return true;
		}
	}
	return false;

	dfs(0);
	if(cycle==-1)return false;
	// return true;
	vector<int> ans;
	vector<int> c;
	int X=-1,Y=-1;
	for(auto to:g[cycle]){
		if(rev(to.S)==pr[cycle])continue;
		if(X==-1)X=to.S;
		else Y=to.S;
	}
	assert(Y!=-1&&X!=-1);
	while(cycle!=0){
		c.pb(pr[cycle]);
		cycle=U[pr[cycle]];
	}
	reverse(all(c));
	for(int x:c)ans.pb(x);

	{
		ans.pb(X);
		ans.pb(rev(X));
		ans.pb(Y);
		ans.pb(rev(Y));
		ans.pb(rev(X));
		ans.pb(X);
		ans.pb(rev(Y));
		ans.pb(Y);
	}

	reverse(all(c));
	for(int x:c)ans.pb(x);
	return ans; 
}

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