Submission #754603

#	Time	Username	Problem	Language	Result	Execution time	Memory
754603		tolbi	Keys (IOI21_keys)	C++17	100 / 100	1361 ms	144352 KiB

keys

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename T> vector<int32_t> normalize(vector<T> &arr){vector<int32_t> rv;rv.resize(arr.size());for (int i = 0; i < rv.size(); ++i){rv[i]=arr[i];}return rv;}
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
const int INF = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "keys.h"
vector<int> comp;
vector<int> pp;
int find(int node){
	if (comp[node]==node) return node;
	return comp[node]=find(comp[node]);
}
int yuk(int node){
	if (pp[node]==node) return pp[node];
	return pp[node]=yuk(pp[node]);
}
vector<int32_t> find_reachable(vector<int32_t> r, vector<int32_t> u, vector<int32_t> v, vector<int32_t> c) {
	int n = r.size();
	int m = u.size();
	vector<int> par(n);
	vector<vector<int>> kard(n);
	for (int i = 0; i < n; ++i)
	{
		kard[i].push_back(i);
	}
	comp.resize(n);
	pp.resize(n);
	vector<int> sz(n,1);
	iota(par.begin(), par.end(), 0ll);
	iota(pp.begin(), pp.end(), 0ll);
	iota(comp.begin(), comp.end(), 0ll);
	queue<int> op;
	vector<set<int>> keys(n);
	vector<map<int,vector<int>>> roads(n);
	vector<int> ss(n);
	vector<vector<int>> ava(n);
	for (int i = 0; i < m; i++){
		roads[u[i]][c[i]].push_back(v[i]);
		roads[v[i]][c[i]].push_back(u[i]);
		ss[u[i]]++;
		ss[v[i]]++;
	}
	for (int i = 0; i < n; ++i)
	{
		op.push(i);
		keys[i].insert(r[i]);
		for (auto it = roads[i][r[i]].begin(); it != roads[i][r[i]].end(); it++){
			ava[i].push_back(*it);
			ss[i]--;
		}
		roads[i].erase(r[i]);
	}
	vector<int> fin;
	int mis = INF;
	queue<int> ne;
	while (op.size()){
		while (op.size()){
			int node = op.front();
			op.pop();
			if (find(node)!=node) continue;
			bool bb = true;
			while (ava[node].size()){
				int nex = ava[node].back();
				ava[node].pop_back();
				if (find(node)==find(nex)){
					nex=yuk(nex);
					while (nex!=node){
						sz[node]+=sz[nex];
						if (kard[node].size()<kard[nex].size()) swap(kard[node],kard[nex]);
						for (int j = 0; j < kard[nex].size(); j++){
							kard[node].push_back(kard[nex][j]);
						}
						sz[nex]=0;
						kard[nex].clear();
						kard[node].push_back(nex);
						if (ss[node]+keys[node].size()<ss[nex]+keys[nex].size()){
							swap(roads[node],roads[nex]);
							swap(keys[node],keys[nex]);
						}
						for (auto it : roads[nex]){
							for (int i = 0; i < it.second.size(); i++){
								if (keys[node].find(it.first)!=keys[node].end()){
									ava[node].push_back(it.second[i]);
									ss[nex]--;
									continue;
								}
								roads[node][it.first].push_back(it.second[i]);
								ss[node]++;
								ss[nex]--;
							}
						}
						roads[nex].clear();
						for (auto it : keys[nex]){
							keys[node].insert(it);
							if (roads[node].count(it)){
								for (auto it2 : roads[node][it]){
									ava[node].push_back(it2);
									ss[node]--;
								}
								roads[node].erase(it);
							}
						}
						keys[nex].clear();
						if (ava[node].size()<ava[nex].size()) swap(ava[node],ava[nex]);
						while (ava[nex].size()){
							ava[node].push_back(ava[nex].back());
							ava[nex].pop_back();
						}
						//jump parent
						pp[nex]=par[nex];
						nex=yuk(nex);
					}
				}
				else {
					par[node]=nex;
					comp[node]=find(nex);
					bb=false;
					break;
				}
			}
			if (bb){
				if (sz[node]==mis){
					for (int i = 0; i < kard[node].size(); i++){
						fin.push_back(kard[node][i]);
					}
				}
				else if (sz[node]<mis){
					mis=sz[node];
					fin.clear();
					for (int i = 0; i < kard[node].size(); i++){
						fin.push_back(kard[node][i]);
					}
				}
			}
		}
		swap(ne,op);
	}
	vector<int> ansarr(n,0);
	for (int i = 0; i < fin.size(); ++i)
	{
		ansarr[fin[i]]=1;
	}
	return ansarr;
}

Compilation message (stderr)

keys.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       for (int j = 0; j < kard[nex].size(); j++){
      |                       ~~^~~~~~~~~~~~~~~~~~
keys.cpp:111:26: 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 < it.second.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
keys.cpp:153:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |      for (int i = 0; i < kard[node].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~~~~~
keys.cpp:160:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |      for (int i = 0; i < kard[node].size(); i++){
      |                      ~~^~~~~~~~~~~~~~~~~~~
keys.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (int i = 0; i < fin.size(); ++i)
      |                  ~~^~~~~~~~~~~~

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