Submission #634175

#	Time	Username	Problem	Language	Result	Execution time	Memory
634175		flappybird	Thousands Islands (IOI22_islands)	C++17	100 / 100	134 ms	22948 KiB

islands

#include "islands.h"

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

#define MAX 201010

int deg[MAX];
vector<int> adj[MAX];
vector<int> radj[MAX];
int chk[MAX];
int vis[MAX];
vector<int> U, V;
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;
	::U = U;
	::V = V;
	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 (1) {
		while (q.size()) {
			int t = q.front();
			chk[t] = 1;
			q.pop();
			for (auto v : radj[t]) if (!chk[v]) {
				deg[v]--;
				if (deg[v] == 0) q.push(v);
			}
		}
		if (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);
					}
					chk[s] = 1;
					s = V[n];
					st.push_back(n);
					break;
				}
			}
			if (deg[s] == 0) return false;
			continue;
		}
		else break;
	}
	vector<int> ans = st;
	int a, b;
	a = b = -1;
	for (auto n : adj[s]) if (!chk[V[n]]) b = a, a = n;
	vector<int> p1, p2, cyc1, cyc2;
	int v;

	p1.push_back(a);
	v = V[a];
	vis[a] = 1;
	while (1) {
		int nn, x;
		for (auto n : adj[v]) {
			x = V[n];
			if (chk[x]) continue;
			nn = n;
			break;
		}
		if (vis[nn]) {
			while (p1.size()) {
				cyc1.push_back(p1.back());
				if (p1.back() == nn) {
					p1.pop_back();
					break;
				}
				p1.pop_back();
			}
			reverse(cyc1.begin(), cyc1.end());
			break;
		}
		p1.push_back(nn);
		vis[nn] = 1;
		v = x;
	}

end1:

	memset(vis, 0, sizeof(vis));

	p2.push_back(b);
	v = V[b];
	vis[b] = 1;
	while (1) {
		int nn, x;
		for (auto n : adj[v]) {
			x = V[n];
			if (chk[x]) continue;
			nn = n;
			break;
		}
		if (vis[nn]) {
			while (p2.size()) {
				cyc2.push_back(p2.back());
				if (p2.back() == nn) {
					p2.pop_back();
					break;
				}
				p2.pop_back();
			}
			reverse(cyc2.begin(), cyc2.end());
			break;
		}
		p2.push_back(nn);
		vis[nn] = 1;
		v = x;
	}

end2:

	memset(vis, 0, sizeof(vis));

	for (auto v : cyc1) vis[v] = 1;
	int c = 0;
	for (auto v : cyc2) if (vis[v]) c = 1;

	for (auto v : p1) ans.push_back(v);
	for (auto v : cyc1) ans.push_back(v);
	reverse(p1.begin(), p1.end());
	for (auto v : p1) ans.push_back(v);
	reverse(p1.begin(), p1.end());

	for (auto v : p2) ans.push_back(v);
	if (c) reverse(cyc2.begin(), cyc2.end());
	for (auto v : cyc2) ans.push_back(v);
	if (c) reverse(cyc2.begin(), cyc2.end());
	reverse(p2.begin(), p2.end());
	for (auto v : p2) ans.push_back(v);
	reverse(p2.begin(), p2.end());

	if (c) {
		reverse(st.begin(), st.end());
		for (auto v : st) ans.push_back(v);
		return ans;
	}

	for (auto v : p1) ans.push_back(v);
	reverse(cyc1.begin(), cyc1.end());
	for (auto v : cyc1) ans.push_back(v);
	reverse(cyc1.begin(), cyc1.end());
	reverse(p1.begin(), p1.end());
	for (auto v : p1) ans.push_back(v);
	reverse(p1.begin(), p1.end());

	for (auto v : p2) ans.push_back(v);
	reverse(cyc2.begin(), cyc2.end());
	for (auto v : cyc2) ans.push_back(v);
	reverse(cyc2.begin(), cyc2.end());
	reverse(p2.begin(), p2.end());
	for (auto v : p2) ans.push_back(v);
	reverse(p2.begin(), p2.end());

	reverse(st.begin(), st.end());
	for (auto v : st) ans.push_back(v);
	return ans;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:91:1: warning: label 'end1' defined but not used [-Wunused-label]
   91 | end1:
      | ^~~~
islands.cpp:123:1: warning: label 'end2' defined but not used [-Wunused-label]
  123 | end2:
      | ^~~~
islands.cpp:120:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |   v = x;
      |   ~~^~~
islands.cpp:88:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |   v = x;
      |   ~~^~~

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