Submission #1267708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267708		LucaLucaM	Keys (IOI21_keys)	C++20	100 / 100	2203 ms	95168 KiB

keys

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>

// https://mzhang2021.github.io/cp-blog/library/
struct SCC {
    int n, ti;
    std::vector<int> num, id, stk;
    std::vector<std::vector<int>> adj, comp;
		std::vector<int> root;

		void init(int _n) {
			n = _n;
			ti = 0;
			num.assign(n, 0);
			id.assign(n, -1);
			adj.resize(n);
			root.resize(n);
			stk.clear();
			comp.clear();
			for (int i = 0; i < n; i++) {
				adj[i].clear();
			}
		}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void build() {
        for (int u=0; u<n; u++)
            if (!num[u])
                dfs(u);
        for (auto v : comp) {
						for (int x : v) {
							root[x] = v[0];
						}
        }
    }

    int dfs(int u) {
        int low = num[u] = ++ti;
        stk.push_back(u);
        for (int v : adj[u]) {
            if (!num[v])
                low = std::min(low, dfs(v));
            else if (id[v] == -1)
                low = std::min(low, num[v]);
        }
        if (low == num[u]) {
            comp.emplace_back();
            do {
                id[stk.back()] = (int) comp.size() - 1;
                comp.back().push_back(stk.back());
                stk.pop_back();
            } while (comp.back().back() != u);
        }
        return low;
    }
};

std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	int n = (int) a.size();
	int m = (int) U.size();
	
	U.resize(2 * m);
	V.resize(2 * m);
	C.resize(2 * m);
	for (int i = m; i < 2 * m; i++) {
		U[i] = V[i - m];
		V[i] = U[i - m];
		C[i] = C[i - m];
	}
	m *= 2;

	std::vector<int> root(n);
	for (int i = 0; i < n; i++) {
		root[i] = i;
	}

	SCC g;

	for (int phase = 0; phase < 20; phase++) {
		std::vector<std::set<int>> keys(n);
		for (int i = 0; i < n; i++) {
			keys[root[i]].insert(a[i]);
		}

		g.init(n);

		for (int i = 0; i < m; i++) {
			int u = U[i], v = V[i];
			int c = C[i];
			if (root[u] == root[v] || keys[root[u]].count(c)) {
				g.addEdge(u, v);
			}
		}


		g.build();

		for (int i = 0; i < n; i++)  {
			root[i] = g.root[i];
		}
	}

	std::vector<int> sz(n, 0);

	for (int i = 0; i < n; i++) {
		sz[root[i]]++;
	}

	std::vector<bool> hasOut(n, false);

	std::vector<std::set<int>> keys(n);
	for (int i = 0; i < n; i++) {
		keys[root[i]].insert(a[i]);
	}
	for (int i = 0; i < m; i++) {
		int u = U[i], v = V[i];
		int c = C[i];
		if (root[u] != root[v] && keys[root[u]].count(c)) {
			hasOut[root[u]] = true;
		}
	}

	int minSize = n;

	for (int i = 0; i < n; i++) {
		if (!hasOut[root[i]]) {
			minSize = std::min(minSize, sz[root[i]]);
		}
	}

	std::vector<int> ret(n, 0);

	for (int i = 0; i < n; i++) {
		if (!hasOut[root[i]]) {
			if (sz[root[i]] == minSize) {
				ret[i] = 1;
			} 
		}
	}

	return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33