Submission #598558

#	Time	Username	Problem	Language	Result	Execution time	Memory
598558		definitelynotmee	Keys (IOI21_keys)	C++17	37 / 100	3075 ms	30728 KiB

keys

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	vector<int> ans(r.size(), 1);
	int n = r.size();

	matrix<pii> g(n);
	for(int i = 0; i < u.size(); i++){
		g[u[i]].push_back({v[i],c[i]});
		g[v[i]].push_back({u[i],c[i]});
	}

	for(int root = 0; root < n; root++){
		vector<int> check(n), got(n);
		matrix<int> whenget(n);

		vector<int> st = {root};

		while(!st.empty()){
			int cur = st.back();
			st.pop_back();
			if(check[cur])
				continue;
			check[cur] = 1;
			got[r[cur]] = 1;
			while(!whenget[r[cur]].empty()){
				st.push_back(whenget[r[cur]].back());
				whenget[r[cur]].pop_back();
			}
			for(pii i : g[cur]){
				if(got[i.ss])
					st.push_back(i.ff);
				else whenget[i.ss].push_back(i.ff);
			}
		}
		ans[root] = accumulate(all(check),0);
	}

	int mini = *min_element(all(ans));
	for(int i = 0; i < n; i++)
		ans[i] = ans[i] == mini;

	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:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~

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