Submission #837424

#	Time	Username	Problem	Language	Result	Execution time	Memory
837424		ymm	Thousands Islands (IOI22_islands)	C++17	0 / 100	1157 ms	2097152 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
 
const int N = 100'010;
int height[N], mnup[N], mxup[N];
vector<int> A[N];
bool vis[N];
bool anc[N];
int mncnt[N];
int kooft[N];
int par[N];
int marg[N];
int mark[N];
int mark2[N];
bool good[N];
 
bool dfs1(int v, int p, int h)
{
	par[v] = p;
	vis[v] = 1;
	anc[v] = 1;
	height[v] = h;
	mnup[v] = N;
	mxup[v] = -N;
	int cnt = 0;
	for (int u : A[v]) {
		if (anc[u]) {
			mnup[v] = min(mnup[v], height[u]);
			mxup[v] = max(mxup[v], height[u]);
			kooft[u]--;
			marg[u]++;
			mark2[v] = 1;
		}
		if (vis[u]) {
			if (par[u] == v)
				good[u] = 1;
			continue;
		}
		auto tmp = dfs1(u, v, h+1);
		cnt += !!marg[v] || tmp;
		mark[u] = !!marg[v];
		marg[v] = 0;
		mnup[v] = min(mnup[v], mnup[u]);
		if (mxup[u] <= height[v])
			mxup[v] = max(mxup[v], mxup[u]);
		mark2[v] |= mark2[u];
	}
	if (cnt >= 2)
		throw 1;
	anc[v] = 0;
	return cnt;
}

void dfs2(int v, int p, int mx)
{
	mx = max(mxup[v], mx);
	mxup[v] = mx;
	for (int u : A[v]) {
		if (u == p)
			continue;
		dfs2(u, v, mx);
	}
}

bool has_back(int v) { return mnup[v] <= height[v]; }

void make_count()
{
	vector<int> vec = {0};
	fill(mncnt, mncnt+N, N);
	mncnt[0] = -1;
	while (vec.size()) {
		int v = vec.back();
		vec.pop_back();
		vis[v] = 1;
		int x = has_back(v)? height[v]: mncnt[v];
		for (int u : A[v]) {
			if (!vis[u]) {
				mncnt[u] = min(mncnt[u], x);
				if (!--kooft[u])
					vec.push_back(u);
			}
		}
	}
}
 
 
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
	Loop (i,0,M) {
		A[U[i]].push_back(V[i]);
		kooft[V[i]]++;
	}
	try {
		dfs1(0, -1, 0);
	} catch(int) {
		return true;
	}
	dfs2(0, -1, -N);
	Loop (i,0,N) {
		if (vis[i])
			continue;
		for (int u : A[i])
			kooft[u]--;
	}
	memset(vis, 0, sizeof(vis));
	make_count();
	Loop (i,0,N) {
		if (has_back(i) && mncnt[i] <= mxup[i] && (mncnt[i] < height[i]-1 || good[i]))
			return true;
	}
	return false;
}

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