Submission #580278

#	Time	Username	Problem	Language	Result	Execution time	Memory
580278		joelau	Keys (IOI21_keys)	C++17	37 / 100	117 ms	20928 KiB

keys

#include <bits/stdc++.h>
using namespace std;

int ans[2005];
bitset<2005> bs, visited;
vector< pair<int,int> > lst[2005];
vector<int> A[2005];
queue<int> q;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int N = r.size();
	for (int i = 0; i < u.size(); ++i) lst[u[i]].emplace_back(v[i],c[i]), lst[v[i]].emplace_back(u[i],c[i]);
	for (int i = 0; i < N; ++i) {
		bs.reset(); visited.reset();
		for (int j = 0; j < N; ++j) A[j].clear();
		q.push(i);
		visited[i] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			if (!bs[r[u]]) {
				bs[r[u]] = 1;
				for (int v: A[r[u]]) if (!visited[v]) {
					visited[v] = 1;
					q.push(v);
				}
			}
			for (auto v: lst[u]) if (!visited[v.first]) {
				if (bs[v.second]) {
					q.push(v.first);
					visited[v.first] = 1;
				}
				else A[v.second].push_back(v.first);
			}
		}
		ans[i] = 0;
		for (int j = 0; j < N; ++j) if (visited[j]) ans[i]++;
	}
	int least = 2e9;
	for (int i = 0; i < N; ++i) least = min(least,ans[i]);
	vector<int> res;
	for (int i = 0; i < N; ++i) res.push_back(ans[i] == least);
	return res;
}

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

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