Submission #599478

#	Time	Username	Problem	Language	Result	Execution time	Memory
599478		CaroLinda	Keys (IOI21_keys)	C++17	37 / 100	3097 ms	39176 KiB

keys

#include <vector>
#include <bits/stdc++.h>

const int MAXN = 3e5+10;

using namespace std;

vector<int> filaChave[MAXN];
int N;
int dsu[MAXN];
vector<pair<int,int> > adj[MAXN];
bool chave[MAXN]; //assume sempre que estah limpa
bool vis[MAXN];

int find(int x){
	return dsu[x] = (x == dsu[x]) ? x : find(dsu[x]);
}

bool join(int a, int b){
	a = find(a);
	b = find(b);

	if(a == b)
		return false;

	if(rand() % 2)
		swap(a,b);

	dsu[a] = b;

	return true;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	N = r.size();

	vector<int> ruins, bons(N);

	iota(bons.begin(),bons.end(), 0);

	for(int i = 0; i < u.size(); i++){
		int a = u[i];
		int b = v[i];

		adj[a].push_back(make_pair(b,c[i]));
		adj[b].push_back(make_pair(a,c[i]));
	}

//	iota(dsu, dsu+N, 0);

	auto fazBfs = [&](int x){
		vector<int> toProcess = {x};

		int ini = 0, ans = 0;
		bool quebra = false;

		vector<int> c;

		while(ini < toProcess.size() && !quebra){
			int y = toProcess[ini++];

			if(vis[y])
				continue;

			ans++;

			vis[y] = true;
			chave[r[y]] = true;

			while(!filaChave[r[y]].empty()){
				toProcess.push_back(filaChave[r[y]].back());
				filaChave[r[y]].pop_back();
			}

			for(auto &e: adj[y]){
				if(join(e.first, y)){
					quebra = true;
					break;
				}

				if(vis[e.first])
					continue;

				if(chave[e.second])
					toProcess.push_back(e.first);
				else{
					filaChave[e.second].push_back(e.first);
					c.push_back(e.second);
				}
			}

		}

		for(auto &e: c)
			filaChave[e].clear();

		for(auto &e: toProcess){
			vis[e] = false;
			chave[r[e]] = false;
		}

		return ans;
	};

	/*while(!bons.empty()){
		vector<int> newBons;

		for(auto &e: bons){
			if(fazBfs(e))
				newBons.push_back(e);
		}

		bons.clear();

		for(auto &e: newBons)
			if(find(e) == e)
				bons.push_back(e);
	}*/

	vector<pair<int,int> > p;
	vector<int> ans(N, 0);


	for(int i = 0; i < N; i++){
		p.push_back(make_pair(fazBfs(i), i));
	}

	sort(p.begin(),p.end());

	int mn = p[0].first;

	for(auto &e: p)
		if(e.first == mn)
			ans[e.second] = 1;

	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:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
keys.cpp: In lambda function:
keys.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   while(ini < toProcess.size() && !quebra){
      |         ~~~~^~~~~~~~~~~~~~~~~~

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