Submission #1060592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060592		jamjanek	Keys (IOI21_keys)	C++17	100 / 100	839 ms	182092 KiB

keys

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

int rozmiar[300010];
int father1[300010];
int father2[300010];
int ojciec[300010];
int find1(int x){
	if(father1[x]==x)return x;
	return father1[x] = find1(father1[x]);
}
void union1(int a, int b){
	a = find1(a);
	b = find1(b);
	if(a!=b)
		father1[b] = a;
}
set<int>klucze[300010];
set<int>graf[300010];
set<pair<int,int>>zablokowane[300010];

int find2(int x){
	if(father2[x]==x)return x;
	return father2[x] = find2(father2[x]);
}
void union2(int a, int b){
	a = find2(a);
	b = find2(b);
	if(rozmiar[a] < rozmiar[b])swap(a,b);
	rozmiar[a]+=rozmiar[b];
	father2[b] = a;
	for(auto j: graf[b])
		graf[a].insert(j);
	for(auto j: klucze[b]){
		if(klucze[a].find(j)!=klucze[a].end())continue;
		klucze[a].insert(j);
		auto pom = zablokowane[a].lower_bound({j,-1});
		while((pom)!=zablokowane[a].end() && (*pom).first==j){
			graf[a].insert((*pom).second);
			zablokowane[a].erase(*pom);
			pom = zablokowane[a].lower_bound({j, -1});
		}
	}
	for(auto j: zablokowane[b]){
		if(klucze[a].find(j.first)!=klucze[a].end())
			graf[a].insert(j.second);
		else
			zablokowane[a].insert(j);
	}
}
vector<int> find_reachable(vector<int>R, vector<int>U, vector<int>V, vector<int>C)
{
	int n, m, a, b, c, i;
  n = R.size();
  m = U.size();
	for(i=0;i<n;i++){
      a = R[i];
		father1[i] = i;
		father2[i] = i;
		rozmiar[i] = 1;
		klucze[i].insert(a);
		ojciec[i] = -1;
	}
	for(i=0;i<m;i++){
      a = U[i], b = V[i], c = C[i];
		if(klucze[a].find(c)!=klucze[a].end())
			graf[a].insert(b);
		else
			zablokowane[a].insert({c,b});
		if(klucze[b].find(c)!=klucze[b].end())
			graf[b].insert(a);
		else
			zablokowane[b].insert({c,a});
	}
	queue<int>kolejka;
	for(i=0;i<n;i++){
		if(graf[i].size()>0)
			kolejka.push(i);
	}
	while(kolejka.size()){
		int x = kolejka.front();
		kolejka.pop();
		x = find2(x);
		ojciec[x] = find2(*(graf[x].begin()));
		//printf("%d %d\n", x, ojciec[x]);
		graf[x].erase(graf[x].begin());
		if(find1(ojciec[x])!=find1(x)){
			union1(x, ojciec[x]);
			continue;
		}
		vector<int>pom;
		int z = ojciec[x];
		while(find2(z)!=find2(x)){
			pom.push_back(z);
			z = ojciec[z];
		}
		pom.push_back(z);
		for(i=1;i<(int)pom.size();i++){
			union2(pom[i-1], pom[i]);
		}
		x = find2(x);
		//printf("po zcaleniu %d\n", x);
		ojciec[x] = -1;
		while(!graf[x].empty() && find2(*graf[x].begin())==x){
			graf[x].erase(graf[x].begin());
		}
		if(graf[x].size()>0)
			kolejka.push(x);
	}
	int wynik = n;
	for(i=0;i<n;i++)
		if(ojciec[find2(i)]==-1)
			wynik = min(wynik, rozmiar[find2(i)]);
	vector<int>answer;
  for(i=0;i<n;i++)
    answer.push_back(ojciec[find2(i)]==-1 && wynik==rozmiar[find2(i)]);
  return answer;
//	for(i=0;i<n;i++)
//		printf("%d ", ojciec[find2(i)]);
//	for(i=0;i<n;i++)
//		printf("%d ", rozmiar[find2(i)]);
}

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