Submission #834973

#	Time	Username	Problem	Language	Result	Execution time	Memory
834973		pavement	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	24 ms	3152 KiB

islands

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

#define pb push_back

int cur_scc;
vector<int> tp, scc_num, sz_scc, adj_from_0;
vector<bool> vis;
vector<vector<int> > adj, adj_t, adj_scc_t, init;

void dfs(int u) {
	if (vis[u]) {
		return;
	}
	vis[u] = 1;
	for (auto v : adj_t[u]) {
		dfs(v);
	}
	tp.pb(u);
}

void collect(int u) {
	if (vis[u]) {
		return;
	}
	vis[u] = 1;
	scc_num[u] = cur_scc;
	for (auto v : adj[u]) {
		collect(v);
	}
}

vector<int> dp(int u) {
	vector<int> cur = init[u];
	if ((int)cur.size() > 1) {
		return cur;
	}
	for (auto v : adj_scc_t[u]) {
		auto tmp = dp(v);
		for (int i : tmp) {
			bool in = 0;
			for (int j : cur) {
				if (i == j) {
					in = 1;
					break;
				}
			}
			if (!in) {
				cur.pb(i);
				if ((int)cur.size() > 1) {
					return cur;
				}
			}
		}
	}
	return cur;
}

namespace ufds {
	vector<int> lnk, sz, num_edges;
	
	void init(int n) {
		lnk.resize(n);
		iota(lnk.begin(), lnk.end(), 0);
		sz.resize(n);
		fill(sz.begin(), sz.end(), 1);
		num_edges.resize(n);
		fill(num_edges.begin(), num_edges.end(), 0);
	}
	int find(int x) {
		if (x == lnk[x]) {
			return x;
		}
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) {
			return;
		}
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		sz[a] += sz[b];
		num_edges[a] += num_edges[b];
		lnk[b] = a;
	}
};

variant<bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) {
	ufds::init(N);
	for (int i = 0; i < M; i++) {
		if (i % 2 == 0) {
			ufds::unite(U[i], V[i]);
			ufds::num_edges[ufds::find(U[i])]++;
		}
	}
	if (ufds::num_edges[ufds::find(0)] != ufds::sz[ufds::find(0)] - 1) {
		return true;
	}
	vis.resize(N);
	scc_num.resize(N);
	adj.resize(N);
	adj_t.resize(N);
	adj_scc_t.resize(N);
	for (int i = 0; i < M; i++) {
		adj[U[i]].pb(V[i]);
		adj_t[V[i]].pb(U[i]);
	}
	for (int i = 0; i < N; i++) {
		dfs(i);
	}
	reverse(tp.begin(), tp.end());
	fill(vis.begin(), vis.end(), 0);
	for (int i : tp) {
		if (!vis[i]) {
			collect(i);
			cur_scc++;
		}
	}
	sz_scc.resize(cur_scc);
	init.resize(cur_scc);
	for (int i = 0; i < N; i++) {
		sz_scc[scc_num[i]]++;
	}
	for (int i = 0; i < M; i++) {
		if (U[i] == 0 && (int)init[scc_num[V[i]]].size() < 2) {
			init[scc_num[V[i]]].pb(i);
		}
		if (scc_num[U[i]] != scc_num[V[i]]) {			
			adj_scc_t[scc_num[V[i]]].pb(scc_num[U[i]]);
		}
	}
	for (int i = 0; i < cur_scc; i++) {
		auto vec = dp(i);
		if (sz_scc[i] > 1 && (int)vec.size() > 1) {
			return true;
		}
	}
	return false;
}

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