Submission #939919

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939919	2024-03-07T00:56:19 Z	beaboss	Keys (IOI21_keys)	C++17	Compilation error	0 ms	0 KB

keys

// Source: https://oj.uz/problem/view/IOI21_candies
// 
#include "keys.h"
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int N = 3e5 + 10;
vpii adj[N];
bool fin[N], vis[N], have[N];
vi vislist, block[N];
vi e;
int here[N], res[N];

int mn = N;

void reset(){
	for (auto val: vislist) {
		have[here[val]]=false;
		vis[val]=false;
	}
	for (auto val: e) block[val].clear();
	vislist.clear();
	e.clear();
}

int bfs(int _) {
	queue<int> q;
	q.push(_);
	vis[_]=true;
	vislist.pb(_);
	int sz = 0;
	while (!q.empty() && sz <= mn) {
		sz++;
		int cur = q.front();
		q.pop();
		// cout << cur << ' ' << here[cur] << endl;
		int key = here[cur];
		for (auto val: block[key]) {
			if (!vis[val]) {
				if (fin[val]) return N; // 
				vislist.pb(val);
				vis[val]=true;
				q.push(val);
				// sz++;
			}
		}

		block[key].clear();

		have[key]=true;
		// cout << ' ' << key << endl;
		for (auto val: adj[cur]) {
			// cout << ' ' << cur << val.f << val.s << key << endl;
			if (vis[val.f]) continue;
			if (have[val.s]) {
				if (fin[val.f]) return N; // 
				vislist.pb(val.f);
				vis[val.f]=true;
				q.push(val.f);
				// sz++;
			} else {
				block[val.s].pb(val.f);
				e.pb(val.s);
			}

		}

	}

	if (sz > mn) return N;

	for (auto val: vislist) res[val] = min(res[val], sz);
		// cout << sz << endl;
	return sz;
}

vi find_reachable(vi c, vi l, vi r, vi v) {

	int n = c.size();
	FOR(i, 0, n) {
		here[i] = c[i];
		
		res[i] = N;
	}
	int m = l.size();

	FOR(i, 0, m) {
		adj[l[i]].pb({r[i], v[i]});
		adj[r[i]].pb({l[i], v[i]});
	}

	vi p(n);
	FOR(i, 0, n) p[i]=i;
	shuffle(p.begin(), p.end());

	for (auto i: p) {
		
		if (!fin[i]) {
			int h = bfs(i);
			res[i] = min(res[i], h);
			// cout << i << h << endl;
			// fin[i]=true;
			// cout << i << h << endl;
			mn = min(mn, res[i]);
			reset();
		}
	}
	vi ans(n, 0);
	FOR(i, 0, n) {
		if (res[i] == mn) {
			ans[i]=1;
		}
	}

	return ans;

}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	vi h = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
// 	for (auto val: h) cout << val << endl;




// }

Compilation message

keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:112:28: error: no matching function for call to 'shuffle(std::vector<int>::iterator, std::vector<int>::iterator)'
  112 |  shuffle(p.begin(), p.end());
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from keys.cpp:4:
/usr/include/c++/10/bits/stl_algo.h:3748:5: note: candidate: 'template<class _RAIter, class _UGenerator> void std::shuffle(_RAIter, _RAIter, _UGenerator&&)'
 3748 |     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3748:5: note:   template argument deduction/substitution failed:
keys.cpp:112:28: note:   candidate expects 3 arguments, 2 provided
  112 |  shuffle(p.begin(), p.end());
      |                            ^