Submission #1059396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059396		Trent	Keys (IOI21_keys)	C++17	9 / 100	1066 ms	645996 KiB

keys

#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef set<int> si;

vi dfn, mi;
vi stk;
vb ist, vis;
int cdfn = 1;
vvi gp;
vi gi;
void tarjan(int c, vvi& adj) {
	assert(!vis[c]);
	mi[c] = dfn[c] = cdfn++;
	stk.push_back(c);
	assert(!ist[c]); ist[c] = true;
	vis[c] = true;
	for(int i : adj[c]) {
		if(!vis[i]) {
			tarjan(i, adj);
		} else if(ist[i]) {
			mi[c] = min(mi[c], dfn[i]);
		}
	}
	if(mi[c] == dfn[c]){
		gp.emplace_back();
		int cur;
		do{
			cur = stk.back();
			gi[cur] = (int) gp.size() - 1;
			stk.pop_back(); ist[cur] = false;
			gp.back().push_back(cur);
		} while(cur != c);
	}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size(), m = u.size();
	int k = 1;
	forR(i, m) k = max(k, c[i] + 1);
	forR(i, n) k = max(k, r[i] + 1);
	int N = n * k;
	vvi adj(N);
	// room i, key j -> i * k + j
	forR(i, n) forR(j, k) if(j != r[i]) adj[i * k + j].push_back(i * k + r[i]);
	forR(i, m) {
		adj[u[i] * k + c[i]].push_back(v[i] * k + c[i]);
		adj[v[i] * k + c[i]].push_back(u[i] * k + c[i]);
	}

	dfn.resize(N); mi.resize(N); ist.resize(N); vis.resize(N); gi.resize(N);
	forR(i, N) if(!vis[i]){
		assert(stk.empty());
		tarjan(i, adj);
	}
	forR(i, N) assert(vis[i]);
	// cerr << gp.size() << '\n';
	// forR(i, N) cerr << gi[i] << ' ';
	// cerr << '\n';

	vi gpt(gp.size());
	forR(i, n) gpt[gi[i * k + r[i]]] += 1;
	vector<si> gAdj(gp.size());
	forR(i, N) for(int j : adj[i]) if(gi[j] != gi[i]) gAdj[gi[i]].insert(gi[j]);
	forR(i, gp.size()) {
		for(int j : gAdj[i]) gpt[i] += gpt[j];
	}
	vi cnt(n);
	forR(i, n) cnt[i] = gpt[gi[i * k + r[i]]];
	int mi = cnt[0];
	forR(i, n) mi = min(mi, cnt[i]);
	vi ans(n);
	forR(i, n) ans[i] = cnt[i] == mi ? 1 : 0;
	return ans;
}

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:3:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                     ^
keys.cpp:69:2: note: in expansion of macro 'forR'
   69 |  forR(i, gp.size()) {
      |  ^~~~

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