Submission #702099

#	Time	Username	Problem	Language	Result	Execution time	Memory
702099		Lobo	Keys (IOI21_keys)	C++17	100 / 100	2798 ms	167920 KiB

keys

#include<bits/stdc++.h>
using namespace std;
const long long inf = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 3e5+10;

int n, m, ds[maxn], dsz[maxn], mark[maxn], nx[maxn];
set<int> keys[maxn];
vector<int> edgatv[maxn];
map<int,vector<int>> edgblk[maxn];
queue<int> q;

int find(int v) {
	if(v == ds[v]) return v;
	return ds[v] = find(ds[v]);
}

void join(int u, int v) {
	if(dsz[u] < dsz[v]) swap(u,v);
	for(auto k : keys[v]) {
		if(edgblk[u].count(k)) {
			for(auto x : edgblk[u][k]) {
				edgatv[u].pb(x);
			}
			edgblk[u].erase(k);
		}
		keys[u].insert(k);
	}

	for(auto X : edgblk[v]) {
		int c = X.fr;
		if(keys[u].count(c)) {
			for(auto x : edgblk[v][c]) {
				edgatv[u].pb(x);
			}
		}
		else {
			for(auto x : edgblk[v][c]) {
				edgblk[u][c].pb(x);
			}
		}
	}

	for(auto x : edgatv[v]) {
		edgatv[u].pb(x);
	}

	ds[v] = u;
	dsz[u]+= dsz[v];
}

void compress(int u) {
	int v = u;
	vector<int> vec;
	while(true) {
		vec.pb(v);
		v = edgatv[v].back();
		v = find(v);
		if(v == u) break;
	}
	int ant = vec[0];
	for(int i = 1; i < vec.size(); i++) {
		join(ant,vec[i]);
		ant = find(ant);
	}

	q.push(find(u));
}

int T;
void dfs(int u) {
	nx[u] = find(nx[u]);
	u = nx[u];
	while(edgatv[u].size() && find(edgatv[u].back()) == u) edgatv[u].pop_back();
	if(edgatv[u].size() == 0) return;

	mark[u] = T;
	int v = edgatv[u].back();
	v = find(v);
	nx[v] = find(nx[v]);
	if(mark[nx[v]] == T) {
		compress(v);
	}
	else {
		dfs(v);
		nx[u] = nx[v];
	}

}

vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
	n = r.size();
	m = U.size();
	for(int i = 0; i < m; i++) {
		int u = U[i];
		int v = V[i];
		int c = C[i];
		edgblk[u][c].pb(v); dsz[u]++;
		edgblk[v][c].pb(u); dsz[v]++;
	}

	for(int i = 0; i < n; i++) {
		ds[i] = i; dsz[i]++;
		keys[i].insert(r[i]); dsz[i]++;
		nx[i] = i;
		if(edgblk[i].count(r[i])) {
			for(auto x : edgblk[i][r[i]]) {
				edgatv[i].pb(x);
			}
			edgblk[i].erase(r[i]);
		}
	}

	for(int i = 0; i < n; i++) {
		q.push(i);
	}

	while(q.size()) {
		int i = q.front(); q.pop();
		if(i != find(i)) continue;
		T++;
		dfs(i);
	}

	for(int i = 0; i < n; i++) {
		if(i != find(i)) continue;
		while(edgatv[i].size() && find(edgatv[i].back()) == i) edgatv[i].pop_back();
	}

	vector<int> ans(n,0);
	map<int,int> fq;
	for(int i = 0; i < n; i++) {
		if(edgatv[find(i)].size() == 0) fq[find(i)]++;
	}
	int mn = inf;
	for(auto x : fq) mn = min(mn,x.sc);
	for(int i = 0; i < n; i++) {
		if(fq[find(i)] == mn && edgatv[find(i)].size() == 0) ans[i] = 1;
	}

	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void compress(int)':
keys.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 1; i < vec.size(); i++) {
      |                 ~~^~~~~~~~~~~~

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