Submission #599509

#	Time	Username	Problem	Language	Result	Execution time	Memory
599509		CaroLinda	Keys (IOI21_keys)	C++17	100 / 100	1199 ms	59188 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], p[MAXN];
vector<pair<int,int> > adj[MAXN];
bool chave[MAXN]; //assume sempre que estah limpa
bool vis[MAXN];
bool ruim[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;

	dsu[b] = a;

	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;
		int quebra = -1;

		vector<int> c;

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

			if(vis[y])
				continue;

			if(find(y) != find(x)){
				quebra = find(y);
				break;
			}

			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(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;
			p[e] = ans;
		}

		return quebra;
	};

	while(!bons.empty()){
		vector<int> newBons, auxBons;

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

		for(int i =0; i < newBons.size(); i++){
			if(newBons[i] == -1){
				ruim[bons[i]] = true;
			}
			else if(!join(newBons[i], bons[i])){
				auxBons.push_back(bons[i]);
			}
		}

		swap(auxBons, bons);
	}

	fill(p, p+N, N);

	for(int i = 0; i < N; i++)
		if(ruim[i])
			fazBfs(i);

	vector<int> ans(N, 0);

	int mn = p[0];
	for(int i = 0; i < N; i++)
		mn = min(mn, p[i]);

	for(int i= 0; i < N; i++)
		if(mn == p[i])
			ans[i] = 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:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
keys.cpp: In lambda function:
keys.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   while(ini < toProcess.size() && quebra == -1){
      |         ~~~~^~~~~~~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i =0; i < newBons.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~

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