Submission #633664

#	Time	Username	Problem	Language	Result	Execution time	Memory
633664		flappybird	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	48 ms	10980 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;

#define MAX 101010

int deg[MAX];
vector<int> adj[MAX];
vector<int> radj[MAX];
int chk[MAX];
int N, M;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	int i;
	::N = N;
	::M = M;
	for (i = 0; i < M; i++) deg[U[i]]++, adj[U[i]].push_back(i), radj[V[i]].push_back(U[i]);
	queue<int> q;
	for (i = 0; i < N; i++) if (!deg[i]) q.push(i);
	int s = 0;
	vector<int> st;
	while (deg[s] <= 1) {
		if (deg[s] == 0) return false;
		for (auto n : adj[s]) {
			if (!chk[V[n]]) {
				for (auto v : radj[s]) if (!chk[v]) {
					deg[v]--;
					if (deg[v] == 0) q.push(v);
				}
				s = V[n];
				st.push_back(n);
				break;
			}
		}
	}
	while (q.size()) {
		int t = q.front();
		q.pop();
		chk[t] = 1;
		for (auto v : radj[t]) if (!chk[v]) {
			deg[v]--;
			if (deg[v] == 0) q.push(v);
		}
		while (deg[s] <= 1) {
			if (deg[s] == 0) return false;
			for (auto n : adj[s]) {
				if (!chk[V[n]]) {
					for (auto v : radj[s]) if (!chk[v]) {
						deg[v]--;
						if (deg[v] == 0) q.push(v);
					}
					s = V[n];
					st.push_back(n);
					break;
				}
			}
		}
	}
	return vector<int>(3, 3);
}

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