Submission #791886

#	Time	Username	Problem	Language	Result	Execution time	Memory
791886		IvanJ	Keys (IOI21_keys)	C++17	100 / 100	560 ms	61120 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 3e5 + 5;

int n, m;
int r[maxn];
int par[maxn];
int dead[maxn];
int vis[maxn];
int lst[maxn];
int has[maxn];
vector<int> todo[maxn];
vector<ii> adj[maxn];
int sz;
vector<int> ans;

int find(int x) {return (x == par[x]) ? x : par[x] = find(par[x]);}
void merge(int x, int y) {par[find(x)] = find(y);}

vector<int> seen, sol;
void reset() {
	for(int i : sol) has[r[i]] = 0;
	for(int i : seen) todo[i].clear();
	seen.clear(), sol.clear();
}

void bfs(int X, int num) {
	lst[X] = num;
	queue<int> q;
	q.push(X);
	
	while(q.size()) {
		int x = q.front();q.pop();
		if(find(x) != X) {
			merge(X, x);
			lst[find(x)] = num;
			reset();
			return;
		}
		if(vis[x]) continue;
		vis[x] = 1, sol.pb(x);
		
		int key = r[x];
		if(has[key] == 0) {
			has[key] = 1;
			for(int i : todo[key]) q.push(i);
			todo[key].clear();
		}
		
		for(ii p : adj[x]) {
			if(has[p.y]) q.push(p.x);
			else todo[p.y].pb(p.x), seen.pb(p.y);
		}
	}
	
	dead[X] = 1;
	if((int)sol.size() < sz)
		sz = (int)sol.size(), ans.clear();
	if((int)sol.size() == sz) 
		for(int i : sol) ans.pb(i);
	reset();
}


vector<int> find_reachable(vector<int> _r, vector<int> u, vector<int> v, vector<int> c) {
	n = (int)_r.size();
	m = (int)u.size();
	for(int i = 0;i < n;i++) r[i] = _r[i];
	
	for(int i = 0;i < m;i++) 
		adj[u[i]].pb({v[i], c[i]}), adj[v[i]].pb({u[i], c[i]});
	
	for(int i = 0;i < n;i++) par[i] = i;
	
	sz = n + 1;
	int cnt = 1;
	while(1) {
		int flag = 0;
		memset(vis, 0, sizeof vis);
		for(int i = 0;i < n;i++) 
			if(find(i) == i && dead[i] == 0 && lst[i] < cnt)
				bfs(i, cnt), flag = 1;
		cnt++;
		if(flag == 0) break;
	}
	
	vector<int> ret(n, 0);
	for(int i : ans) 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