Submission #441872

#	Time	Username	Problem	Language	Result	Execution time	Memory
441872		Stickfish	Keys (IOI21_keys)	C++17	0 / 100	4 ms	7372 KiB

keys

#include <vector>
#include <bitset>
using namespace std;

const int MAXN = 3e5 + 123;
vector<int> edg[MAXN];
int keyget[MAXN];
int keyneed[MAXN];
bitset<MAXN> used;

vector<int> solve_quad(int n){
	vector<int> ans(n);
	bitset<MAXN> used_cl;
	vector<vector<int>> reachable(n);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			used[j] = used_cl[j] = 0;
			reachable[j].clear();
		}
		vector<int> stck = {i};
		while(stck.size()){
			int v = stck.back();
			used[v] = used_cl[keyget[v]] = 1;
			for(auto u : reachable[keyget[v]]){
				stck.push_back(u);
			}
			reachable[keyget[v]].clear();
			stck.pop_back();
			for(auto u : edg[v]){
				if(used[u])
					continue;
				if(used_cl[keyneed[u]]){
					stck.push_back(u);
				} else {
					reachable[keyneed[u]].push_back(u);
				}
			}
		}
		ans[i] = used.count() - 1;
	}
	return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();
	for(int i = 0; i < n; ++i){
		keyget[i] = r[i];
		keyneed[i] = c[i];
	}
	for(int i = 0; i < m; ++i){
		edg[u[i]].push_back(v[i]);
		edg[v[i]].push_back(u[i]);
	}
	if(n <= 2000 && m <= 2000){
		return solve_quad(n);
	}
}

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:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^

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