Submission #1043268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043268		AmirAli_H1	Keys (IOI21_keys)	C++17	100 / 100	1247 ms	95860 KiB

keys

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

const int maxn = 3e5 + 7;
const int maxlg = 20;

int n, m;
vector<int> adj[maxn], adjr[maxn];
int val[maxn], arr[maxn];
int p[maxn]; vector<int> ls[maxn];
vector<pair<pii, int>> E;
int mark[maxn], col[maxn], c = 0;
bool M[maxn], ok[maxn]; vector<int> vc;
vector<int> ans;

bool cmp(int i, int j) {
	return (val[i] < val[j]);
}

bool is_ok(int u, int c) {
	int j = lower_bound(all(ls[u]), c) - ls[u].begin();
	return (j < len(ls[u]) && ls[u][j] == c);
}

void dfs(int v) {
	mark[v] = 1;
	for (int u : adj[v]) {
		if (!mark[u]) dfs(u);
	}
	vc.pb(v);
}

void dfsr(int v) {
	mark[v] = 1; col[v] = c;
	for (int u : adjr[v]) {
		if (!mark[u]) dfsr(u);
	}
}

void scc() {
	fill(mark, mark + n, 0); vc.clear();
	for (int i = 0; i < n; i++) {
		if (!mark[i]) dfs(i);
	}
	reverse(all(vc));
	
	fill(mark, mark + n, 0); c = 0;
	for (int i : vc) {
		if (!mark[i]) {
			dfsr(i); c++;
		}
	}
}

void fix_edges() {
	for (int i = 0; i < n; i++) {
		adj[i].clear(); adjr[i].clear();
		ls[i].clear(); M[i] = 0;
	}
	for (int j = 0; j < n; j++) {
		int i = arr[j];
		ls[p[i]].pb(val[i]);
		M[p[i]] = 1;
	}
	
	for (auto f : E) {
		int u = f.F.F, v = f.F.S, c = f.S;
		u = p[u]; v = p[v];
		if (u == v) continue;
		if (is_ok(u, c)) {
			adj[u].pb(v); adjr[v].pb(u);
			M[u] = 0;
		}
		if (is_ok(v, c)) {
			adj[v].pb(u); adjr[u].pb(v);
			M[v] = 0;
		}
	}
}

void solve() {
	fix_edges();
	scc();
	for (int i = 0; i < n; i++) p[i] = col[p[i]];
}

vector<int> find_reachable(vector<int> rx, vector<int> ux, vector<int> vx, vector<int> cx) {
	n = len(rx); m = len(ux);
	for (int i = 0; i < n; i++) val[i] = rx[i];
	iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
	
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i], c = cx[i];
		E.pb(Mp(Mp(u, v), c));
	}
	
	iota(p, p + n, 0);
	for (int T = 0; T < maxlg; T++) {
		solve();
	}
	
	int mn = n; fix_edges();
	for (int i = 0; i < n; i++) {
		if (!M[i]) continue;
		if (len(ls[i]) < mn) mn = len(ls[i]);
	}
	
	fill(ok, ok + n, 0);
	ans.clear(); ans.resize(n);
	for (int i = 0; i < n; i++) {
		if (!M[i]) continue;
		if (len(ls[i]) == mn) ok[i] = 1;
	}
	for (int i = 0; i < n; i++) ans[i] = ok[p[i]];
	return ans;
}

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