Submission #1235602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235602		AMnu	Thousands Islands (IOI22_islands)	C++20	100 / 100	66 ms	20900 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 1e5+5;

int st, deg[MAXN], vis[MAXN], len[6];
pii nxt[MAXN];
bool stop;
vector <int> in[MAXN], ans;
vector <pii> out[MAXN];

void del(int x) {
	deg[x]--;
	for (int y : in[x]) {
		deg[y]--;
		if (!deg[y]) {
			del(y);
		}
	}
}

pii find(int x) {
	for (pii y : out[x]) {
		if (deg[y.fi] > 0) {
			return y;
		}
	}
	return {-1,-1};
}

void goback(int x) {
	vector <int> r;
	int y = x;
	do {
		r.push_back(nxt[y].se);
		y = nxt[y].fi;
	}
	while (y != x);
	reverse(r.begin(),r.end());
	for (int a : r) {
		ans.push_back(a);
	}
}

void resail(int x) {
	vis[x] += 2;
	if (vis[x] == 3) {
		goback(x);
		stop = 1;
		vis[x] = 0;
		return;
	}
	if (vis[x] == 4) {
		len[4] = ans.size();
		return;
	}
	int z = ans.size();
	ans.push_back(nxt[x].se);
	resail(nxt[x].fi);
	if (vis[x] == 4) {
		vis[x] = 0;
		len[3] = z;
	}
	if (vis[nxt[x].fi] == 0) {
		vis[x] = 0;
		ans.push_back(nxt[x].se);
	}
}

void sail(int x) {
	vis[x]++;
	if (vis[x] == 2) {
		len[2] = ans.size();
		return;
	}
	int z = ans.size();
	ans.push_back(nxt[x].se);
	sail(nxt[x].fi);
	if (vis[x] == 2) {
		vis[x] = 3;
		len[1] = z;
	}
	if (vis[nxt[x].fi] == 3 || vis[nxt[x].fi] == 0) {
		if (vis[nxt[x].fi] == 3) {
			vis[nxt[x].fi] = 1;
		}
		vis[x] = 0;
		ans.push_back(nxt[x].se);
	}
}

variant<bool,vector<int>> find_journey(int N,int M,vector<int>U,vector<int>V) {
	for (int i=0;i<M;i++) {
		deg[U[i]]++;
		in[V[i]].push_back(U[i]);
		out[U[i]].push_back({V[i],i});
	}
	for (int i=0;i<N;i++) {
		if (!deg[i]) {
			del(i);
		}
	}
	while (deg[st] < 2) {
		if (deg[st] < 1) {
			return false;
		}
		pii x = find(st);
		del(st);
		st = x.fi;
		ans.push_back(x.se);
	}
	len[0] = ans.size();
	for (int i=0;i<N;i++) {
		if (deg[i] > 0) {
			nxt[i] = find(i);
		}
	}
	for (pii y : out[st]) {
		if (deg[y.fi] > 0) {
			nxt[N] = y;
		}
	}
	sail(st);
	if (vis[st] == 3) {
		vis[st] = 1;
	}
	ans.push_back(nxt[N].se);
	resail(nxt[N].fi);
	ans.push_back(nxt[N].se);
	len[5] = ans.size();
	if (!stop) {
		for (int i=len[0];i<len[1];i++) {
			ans.push_back(ans[i]);
		}
		for (int i=len[2]-1;i>=len[1];i--) {
			ans.push_back(ans[i]);
		}
		for (int i=len[2];i<len[3];i++) {
			ans.push_back(ans[i]);
		}
		for (int i=len[4]-1;i>=len[3];i--) {
			ans.push_back(ans[i]);
		}
		for (int i=len[4];i<len[5];i++) {
			ans.push_back(ans[i]);
		}
	}
	for (int i=len[0]-1;i>=0;i--) {
		ans.push_back(ans[i]);
	}
	return ans;
}

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