Submission #559494

#	Time	Username	Problem	Language	Result	Execution time	Memory
559494		8e7	Keys (IOI21_keys)	C++17	100 / 100	1046 ms	351304 KiB

keys

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second

unordered_set<int> se[maxn];
unordered_map<int, vector<int> > adj[maxn];

//vector<pii> adj[maxn];
queue<int> to[maxn];
int par[maxn];
bool vis[maxn], stop[maxn], done[maxn];
int ed[maxn], siz[maxn], as[maxn];

void ini(int n) {
	for (int i = 0;i < n;i++) par[i] = i;
}
int find(int n) {
	return par[n] == n ? n : (par[n] = find(par[n]));
}
void Union(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	debug("merge", a, b);
	if (se[a].size() + as[a] + to[a].size() < se[b].size() + as[b] + to[b].size()) swap(a, b);
	//a <-- b
	for (auto x:adj[b]) {
		int c = x.ff;
		if (se[a].find(c) != se[a].end()) {
			for (int v:x.ss) to[a].push(v);	
		} else {
			adj[a][c].insert(adj[a][c].end(), x.ss.begin(), x.ss.end());
			as[a] += x.ss.size();
		}
	}	
	adj[b].clear();
	for (auto c:se[b]) {
		if (adj[a].find(c) != adj[a].end()) {
			for (int v:adj[a][c]) to[a].push(v);
			as[a] -= adj[a][c].size();
			adj[a].erase(c);
		} 
		se[a].insert(c);
	}
	while (to[b].size()) {
		to[a].push(to[b].front()); to[b].pop();
	}
	par[b] = a;
}
void walk(int st) {
	vector<int> path;
	int cur = find(st);
	while (true) {
		debug(cur, to[cur].size());
		cur = find(cur);
		vis[cur] = 1;
		path.push_back(cur);
		while (to[cur].size() && find(to[cur].front()) == cur) to[cur].pop();
		if (to[cur].size() == 0) {
			stop[cur] = 1;
			break;
		} else {
			int nxt = find(to[cur].front());to[cur].pop();	
			debug(cur, nxt, done[nxt], vis[nxt]);
			if (done[nxt]) {
				break;
			} else if (vis[nxt]) {
				int tmp = find(ed[nxt]);	
				while (nxt != cur) {
					Union(nxt, tmp);
					nxt = tmp;
					tmp = find(ed[nxt]);
				}
			} else {
				ed[cur] = nxt;
				cur = nxt;
			}
		}	
	}
	for (int i:path) done[find(i)] = 1;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), m = u.size();	
	ini(n);
	for (int i = 0;i < n;i++) {
		se[i].insert(r[i]);
	}	
	for (int i = 0;i < m;i++) {
		if (r[u[i]] == c[i]) {
			to[u[i]].push(v[i]);
		} else {
			adj[u[i]][c[i]].push_back(v[i]);
			as[u[i]]++;
		} 
		if (r[v[i]] == c[i]) {
			to[v[i]].push(u[i]);	
		} else {
			adj[v[i]][c[i]].push_back(u[i]);
			as[v[i]]++;
		}
	}
	for (int i = 0;i < n;i++) {
		if (!done[find(i)]) {
			debug("walk", i);
			walk(i);
		}
	}
	for (int i = 0;i < n;i++) siz[find(i)]++;
	int mi = 1<<30;
	pary(stop, stop + n);
	for (int i = 0;i < n;i++) {
		if (stop[i]) {
			mi = min(mi, siz[i]);
		}
	}
	vector<int> ans(n, 0);
	for (int i = 0;i < n;i++) {
		if (siz[find(i)] == mi && stop[find(i)]) ans[i] = 1;
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void Union(int, int)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
keys.cpp:39:2: note: in expansion of macro 'debug'
   39 |  debug("merge", a, b);
      |  ^~~~~
keys.cpp: In function 'void walk(int)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
keys.cpp:69:3: note: in expansion of macro 'debug'
   69 |   debug(cur, to[cur].size());
      |   ^~~~~
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
keys.cpp:79:4: note: in expansion of macro 'debug'
   79 |    debug(cur, nxt, done[nxt], vis[nxt]);
      |    ^~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
keys.cpp:120:4: note: in expansion of macro 'debug'
  120 |    debug("walk", i);
      |    ^~~~~
keys.cpp:13:19: warning: statement has no effect [-Wunused-value]
   13 | #define pary(...) 0
      |                   ^
keys.cpp:126:2: note: in expansion of macro 'pary'
  126 |  pary(stop, stop + n);
      |  ^~~~

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