Submission #1053005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053005		tolbi	Keys (IOI21_keys)	C++17	100 / 100	894 ms	140884 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int> sz;
	vector<int> par;
	DSU(int n){
		sz.resize(n,1);
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	}
	void merge(int a, int b){
		sz[b]+=sz[a];
		sz[a]=0;
		par[a]=b;
	}
};
struct node{
	set<int> keys;
	map<int,vector<int>> roads;
	vector<int> to;
	bool operator<(const node &ot)const{
		return (keys.size()+roads.size()+to.size())<(ot.keys.size()+ot.roads.size()+ot.to.size());
	};
	void process(){
		vector<int> sil;
		for (auto [k,it] : roads){
			if (keys.find(k)!=keys.end()){
				sil.push_back(k);
				for (auto it2 : it){
					to.push_back(it2);
				}
			}
		}
		for (auto it : sil) roads.erase(it);
	}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
	DSU dsu(n);
	DSU compress(n);
	vector<node> arr(n);
	for (int i = 0; i < n; i++){
		arr[i].keys.insert(r[i]);
	}
	for (int i = 0; i < u.size(); ++i)
	{
		arr[u[i]].roads[c[i]].push_back(v[i]);
		arr[v[i]].roads[c[i]].push_back(u[i]);
	}
	queue<int> process;
	for (int i = 0; i < n; ++i)
	{
		arr[i].process();
		process.push(i);
	}
	while (process.size()){
		int node = process.front();
		process.pop();
		if (par[node]!=node) continue;
		while (arr[node].to.size()){
			int git = arr[node].to.back();
			arr[node].to.pop_back();
			if (dsu.find(git)==node){
				git=compress.find(git);
				while (git!=node){
					compress.merge(git,node);
					if (arr[node]<arr[git]) swap(arr[git],arr[node]);
					while (arr[git].to.size()){
						arr[node].to.push_back(arr[git].to.back());
						arr[git].to.pop_back();
					}
					while (arr[git].keys.size()){
						auto it = *arr[git].keys.begin();
						if (arr[node].roads.count(it)){
							for (auto &hh : arr[node].roads[it]){
								arr[node].to.push_back(hh);
							}
							arr[node].roads.erase(it);
						}
						arr[node].keys.insert(it);
						arr[git].keys.erase(arr[git].keys.begin());
					}
					for (auto [k,it] : arr[git].roads){
						if (arr[node].keys.find(k)!=arr[node].keys.end()){
							for (auto &it2 : it){
								arr[node].to.push_back(it2);
							}
						}
						else {
							for (auto &it2 : it){
								arr[node].roads[k].push_back(it2);
							}
						}
					}
					arr[git].roads.clear();
					git=compress.find(par[git]);
				}
			}
			else {
				dsu.merge(node,git);
				par[node]=git;
				process.push(dsu.find(node));
				break;
			}
		}
	}

	vector<int> ans;
	int sz;
	for (int i = 0; i < n; i++){
		if (dsu.find(i)==i){
			if (ans.size()==0 || compress.sz[i]<sz){
				ans.clear();
				sz=compress.sz[i];
				ans.push_back(i);
			}
			else if (compress.sz[i]==sz){
				ans.push_back(i);
			}
		}
	}
	vector<int> ret(n,0);
	for (auto it : ans) ret[it]=1;
	for (int i = 0; i < n; ++i)
	{
		if (ret[compress.find(i)]) ret[i]=1;	
	}
	return ret;
}

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:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < u.size(); ++i)
      |                  ~~^~~~~~~~~~
keys.cpp:123:9: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  123 |    else if (compress.sz[i]==sz){
      |         ^~

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