Submission #837396

#	Time	Username	Problem	Language	Result	Execution time	Memory
837396		ymm	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	32 ms	11884 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];
vector<int> A[N];
bool vis[N];
bool anc[N];
int cnt[N];
int kooft[N];
int par[N];
int marg[N];
 
bool dfs1(int v, int p, int h)
{
	par[v] = p;
	vis[v] = 1;
	anc[v] = 1;
	height[v] = h;
	mnup[v] = N;
	int cnt = 0;
	for (int u : A[v]) {
		if (anc[u]) {
			mnup[v] = min(mnup[v], height[u]);
			kooft[u]--;
			marg[u]++;
		}
		if (vis[u])
			continue;
		auto tmp = dfs1(u, v, h+1);
		cnt += !!marg[v] || tmp;
		marg[v] = 0;
		mnup[v] = min(mnup[v], mnup[u]);
	}
	if (cnt >= 2)
		throw 1;
	anc[v] = 0;
	return cnt;
}
 
void make_count()
{
	vector<int> vec = {0};
	cnt[0] = 1;
	while (vec.size()) {
		int v = vec.back();
		vec.pop_back();
		vis[v] = 1;
		for (int u : A[v]) {
			if (!vis[u]) {
				cnt[u] += cnt[v];
				cnt[u] = min(cnt[u], 2);
				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;
	}
	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 (cnt[i] >= 2 && mnup[i] <= height[i])
			return true;
	}
	return false;
}

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