Submission #939924

#	Time	Username	Problem	Language	Result	Execution time	Memory
939924		beaboss	Keys (IOI21_keys)	C++17	100 / 100	655 ms	54124 KiB

keys

// Source: https://oj.uz/problem/view/IOI21_candies
// 
#include "keys.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 3e5 + 10;
vpii adj[N];
bool fin[N], vis[N], have[N];
vi vislist, block[N];
vi e;
int here[N], res[N];

int mn = N;

void reset(){
	for (auto val: vislist) {
		have[here[val]]=false;
		vis[val]=false;
	}
	for (auto val: e) block[val].clear();
	vislist.clear();
	e.clear();
}

int bfs(int _) {
	queue<int> q;
	q.push(_);
	vis[_]=true;
	vislist.pb(_);
	int sz = 0;
	while (!q.empty() && sz <= mn) {
		sz++;
		int cur = q.front();
		q.pop();
		// cout << cur << ' ' << here[cur] << endl;
		int key = here[cur];
		for (auto val: block[key]) {
			if (!vis[val]) {
				if (fin[val]) return N; // 
				vislist.pb(val);
				vis[val]=true;
				q.push(val);
				// sz++;
			}
		}

		block[key].clear();

		have[key]=true;
		// cout << ' ' << key << endl;
		for (auto val: adj[cur]) {
			// cout << ' ' << cur << val.f << val.s << key << endl;
			if (vis[val.f]) continue;
			if (have[val.s]) {
				if (fin[val.f]) return N; // 
				vislist.pb(val.f);
				vis[val.f]=true;
				q.push(val.f);
				// sz++;
			} else {
				block[val.s].pb(val.f);
				e.pb(val.s);
			}

		}

	}

	if (sz > mn) return N;

	for (auto val: vislist) res[val] = min(res[val], sz);
		// cout << sz << endl;
	return sz;
}

vi find_reachable(vi c, vi l, vi r, vi v) {


	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int n = c.size();
	FOR(i, 0, n) {
		here[i] = c[i];
		
		res[i] = N;
	}
	int m = l.size();

	FOR(i, 0, m) {
		adj[l[i]].pb({r[i], v[i]});
		adj[r[i]].pb({l[i], v[i]});
	}

	vi p(2*m);
	FOR(i, 0, m) {
		p[2*i]=l[i];
		p[2*i+1]=r[i];
	}
	// vi p(n);
	// FOR(i, 0, n) p[i]=i;
	shuffle(p.begin(), p.end(), rng);

	for (auto i: p) {
		
		if (!fin[i]) {
			int h = bfs(i);
			res[i] = min(res[i], h);
			// cout << i << h << endl;
			fin[i]=true;
			// cout << i << h << endl;
			mn = min(mn, res[i]);
			reset();
		}
	}

	FOR(i, 0, n) {
		
		if (!fin[i]) {
			int h = bfs(i);
			res[i] = min(res[i], h);
			// cout << i << h << endl;
			fin[i]=true;
			// cout << i << h << endl;
			mn = min(mn, res[i]);
			reset();
		}
	}

	vi ans(n, 0);
	FOR(i, 0, n) {
		if (res[i] == mn) {
			ans[i]=1;
		}
	}

	return ans;

}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	vi h = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// 	for (auto val: h) cout << val << endl;




// }

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