Submission #1043000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043000		Soumya1	Keys (IOI21_keys)	C++17	100 / 100	829 ms	123580 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
struct DSU_Path {
	vector<int> par;
	int n;
	DSU_Path() { }
	DSU_Path(int _n) {
		n = _n;
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {
		return par[u] = (u == par[u] ? u : find(par[u]));
	}
	void merge(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		par[u] = v;
	}
};
struct SCC {
	int n;
	vector<int> par, sz;
	vector<set<int>> all;
	vector<set<pair<int, int>>> good, bad;
	SCC(int _n) {
		n = _n;
		sz.assign(n, 1);
		par.resize(n);
		all.resize(n);
		good.resize(n), bad.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {
		return par[u] = (u == par[u] ? u : find(par[u]));
	}
	void merge(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		if (sz[u] > sz[v]) swap(u, v);
		sz[v] += sz[u];
		par[u] = v;
		for (int k : all[u]) {
			while (true) {
				auto it = bad[v].lower_bound({k, -5});
				if (it != bad[v].end() && (*it).first == k) {
					bad[v].erase(*it);
					good[v].insert(*it);
				} else {
					break;
				}
			}
			all[v].insert(k);
		}
		all[u].clear();
		for (auto e : good[u]) good[v].insert(e);
		good[u].clear();
		for (auto e : bad[u]) {
			if (all[v].count(e.first)) good[v].insert(e);
			else bad[v].insert(e);
		}
		bad[u].clear();
	}
};
vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size();
	vector<int> succ(n);
	DSU_Path paths = DSU_Path(n);
	SCC scc = SCC(n);
	for (int i = 0; i < n; i++) succ[i] = i;
	for (int i = 0; i < n; i++) {
		scc.all[i].insert(r[i]);
	}
	for (int i = 0; i < u.size(); i++) {
		if (scc.all[u[i]].count(c[i])) scc.good[u[i]].insert({c[i], v[i]});
		else scc.bad[u[i]].insert({c[i], v[i]});
		if (scc.all[v[i]].count(c[i])) scc.good[v[i]].insert({c[i], u[i]});
		else scc.bad[v[i]].insert({c[i], u[i]});
	}
	for (int i = 0; i < n; i++) {
		if (succ[i] != i) continue;
		int root = scc.find(i);
		while (!scc.good[root].empty()) {
			auto [c, v] = *scc.good[root].begin();
			scc.good[root].erase(scc.good[root].begin());
			if (paths.find(root) != paths.find(v)) {
				succ[scc.find(i)] = v;
				paths.merge(paths.find(i), v);
				break;
			} else {
				v = scc.find(v);
				while (v != root) {
					scc.merge(v, root);
					v = succ[v];
					root = scc.find(root), v = scc.find(v);
				}
			}
			root = scc.find(root);
		}
	}
	int mn = n;
	set<int> good_components;
	for (int i = 0; i < n; i++) {
		if (paths.find(i) == i) mn = min(mn, scc.sz[scc.find(i)]);
	}

	for (int i = 0; i < n; i++) {
		if (paths.find(i) == i && scc.sz[scc.find(i)] == mn) good_components.insert(scc.find(i));
	}
	vector<int> good;
	for (int i = 0; i < n; i++) {
		if (good_components.count(scc.find(i))) good.push_back(i);
	}
	vector<int> ans(n);
	for (int i : good) ans[i] = 1;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

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