Submission #830427

#	Time	Username	Problem	Language	Result	Execution time	Memory
830427		NothingXD	Keys (IOI21_keys)	C++17	100 / 100	549 ms	106980 KiB

keys

#include <bits/stdc++.h>

using namespace std;

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

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 3e5 + 10;

int n, m, r[maxn], comp[maxn], st[maxn];
vector<pii> g[maxn];
int ans = maxn;
vector<int> res, ver[maxn], rej[maxn];
bool vis[maxn], bad[maxn], mark[maxn], expand;
vector<int> going;

void merge(int u, int v){
	bool flg = true;
	if ((u = comp[u]) == (v = comp[v])) return;
//	debug(u, v);
	if (ver[u].size() < ver[v].size()){
		swap(u, v);
		flg = false;
	}
	for (auto x: ver[v]){
		if (x == v) continue;
		comp[x] = u;
		ver[u].push_back(x);
	}
	if (flg) st[u] = st[v];
	comp[v] = u;
	ver[u].push_back(v);
//	debug(u, st[u]);
}

void dfs(int v){
//	debug("dfs", v);
	going.push_back(v);
	vis[v] = true;
	mark[r[v]] = true;
	while(!rej[r[v]].empty() && !expand){
		int u = rej[r[v]].back();
		rej[r[v]].pop_back();
		if (bad[u]){
			int x = comp[v];
			for (auto y: ver[x]){
				bad[y] = true;
			}
			expand = true;
			return;
		}
		else if (comp[u] != comp[v]){
			merge(v, u);
			expand = true;
			return;
		}
		else if (!vis[u]) dfs(u);
	}
	for (auto [u, w]: g[v]){
		if (expand) return;
		if (!mark[w]){
			rej[w].push_back(u);
			continue;
		}
		if (bad[u]){
			int x = comp[v];
			for (auto y: ver[x]){
				bad[y] = true;
			}
			expand = true;
			return;
		}
		else if (comp[u] != comp[v]){
			merge(v, u);
			expand = true;
			return;
		}
		else if (!vis[u]) dfs(u);
	}
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
	n = R.size();
	m = C.size();
	for (int i = 0; i < n; i++){
		r[i] = R[i];
		comp[i] = i;
		st[i] = i;
		ver[i].push_back(i);
	}
	for (int i = 0; i < m; i++){
		g[U[i]].push_back({V[i], C[i]});
		g[V[i]].push_back({U[i], C[i]});
	}

	int cnt = 1;
	for (int iii = 0; iii < 20; iii++) {
//		debug(cnt);
		cnt++;
		memset(vis, false, sizeof vis);
		for (int i = 0; i < n; i++){
			int v = st[comp[i]];
			if (!vis[v] && !bad[v]){
				expand = false;
			//	debug(v);
				going.clear();
				dfs(v);
			//	debug(expand);
				if (!expand){
					vector<int> tmp;
					for (auto x: ver[comp[i]]){
						bad[x] = true;
						if (vis[x]) tmp.push_back(x);
						vis[x] = true;
					}
					if (tmp.size() < ans){
						ans = tmp.size();
						res.clear();
					}
					if (tmp.size() == ans){
						for (auto x: tmp) res.push_back(x);
					}
				}
				else{
					vis[st[comp[i]]] = true;
				}
				v = comp[v];
				for (auto x: going){
					mark[r[x]] = false;
					for (auto [u, w]: g[x]){
						rej[w].clear();
					}
				}
			}
		}
	}
	vector<int> answer(n, 0);
	for (auto x: res) answer[x] = 1;
	return answer;
}

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:130:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |      if (tmp.size() < ans){
      |          ~~~~~~~~~~~^~~~~
keys.cpp:134:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |      if (tmp.size() == ans){
      |          ~~~~~~~~~~~^~~~~~

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