제출 #459232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
459232		Peti	열쇠 (IOI21_keys)	C++17	100 / 100	2325 ms	141136 KiB

keys

#include <bits/stdc++.h>

using namespace std;

const int maxn = (int)3e5+1;

vector<map<int, vector<int>>> elek;
vector<vector<int>> g;
vector<set<int>> keys;
vector<int> osok, mely, meret, pontdb;
vector<bool> volt, kesz, kiel;
int n;

int os(int x) { return osok[x] == -1 ? x : osok[x] = os(osok[x]); }

void unio(int a, int b){
	//cout<<"union"<<endl;
	a = os(a);
	b = os(b);
	if(a == b){
		//cout<<"end union"<<endl;
		return;
	}
	if(mely[a] < mely[b]) swap(a, b);

	if(meret[a] < meret[b]){
		swap(g[a], g[b]);
		swap(elek[a], elek[b]);
		swap(keys[a], keys[b]);
	}

	g[a].insert(g[a].end(), g[b].begin(), g[b].end());
	for(const int &x : keys[b]){
		if(keys[a].insert(x).second){
			auto it = elek[a].find(x);
			if(it != elek[a].end()){
				g[a].insert(g[a].end(), it->second.begin(), it->second.end());
				elek[a].erase(it);
			}
		} else
			meret[a]--;
	}
	for(auto &d : elek[b]){
		if(keys[a].count(d.first)){
			g[a].insert(g[a].begin(), d.second.begin(), d.second.end());
		} else{
			vector<int> &v = elek[a][d.first];
			v.insert(v.end(), d.second.begin(), d.second.end());
		}
	}

	osok[b] = a;
	meret[a] += meret[b];
	pontdb[a] += pontdb[b];
	mely[a] += (int)(mely[a] == mely[b]);
	kiel[a] = kiel[a] || kiel[b];
	//cout<<"end union"<<endl;
}

int pont[maxn];
void bejar(int s){
	//cout<<"start"<<endl;
	int x = 0;
	pont[x++] = s;
	while (x > 0)
	{
		//cout<<x<<' '<<pont[x-1]<<'\n';
		int p = pont[x-1];
		//cout<<"node: "<<p<<'\n';
		volt[p] = true;
		if(g[p].empty()){
			//cout<<"case 1"<<endl;
			--x;
			kesz[p] = true;
			if(x > 0)
				kiel[pont[x-1]] = true;
			//cout<<"back "<<p<<'\n';
		} else if(volt[os(g[p].back())] && !kesz[os(g[p].back())]){
			//cout<<"case 2"<<endl;
			int temp = os(g[p].back());
			g[p].pop_back();
			while (pont[x-1] != temp)
			{
				unio(pont[x-1], pont[x-2]);
				--x;
			}
			pont[x-1] = os(p);
		} else if(!volt[os(g[p].back())]){
			//cout<<"case 3"<<endl;
			pont[x++] = os(g[p].back());
			g[p].pop_back();
		} else{
			//cout<<"case 4"<<endl;
			kiel[p] = true;
			g[p].pop_back();
		}
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = (int)r.size();
	g.resize(n);
	elek.resize(n);
	keys.resize(n);
	osok.assign(n, -1);
	mely.assign(n, 0);
	meret.assign(n, 1);
	pontdb.assign(n, 1);
	volt.assign(n, false);
	kiel.assign(n, false);
	kesz.assign(n, false);

	for(int i = 0; i < n; i++)
		keys[i].insert(r[i]);

	for(int i = 0; i < (int)u.size(); i++){
		++meret[u[i]];
		++meret[v[i]];
		if(r[u[i]] == c[i])
			g[u[i]].push_back(v[i]);
		else
			elek[u[i]][c[i]].push_back(v[i]);
		if(r[v[i]] == c[i])
			g[v[i]].push_back(u[i]);
		else
			elek[v[i]][c[i]].push_back(u[i]);
	}

	for(int i = 0; i < n; i++)
		if(!volt[os(i)])
			bejar(os(i));

	int legk = maxn;
	for(int i = 0; i < n; i++)
		if(!kiel[os(i)])
			legk = min(legk, pontdb[os(i)]);

	vector<int> ret(n, 0);
	for(int i = 0; i < n; i++){
		//cout<<i<<": "<<os(i)<<' '<<pontdb[os(i)]<<' '<<kiel[os(i)]<<'\n';
		if(!kiel[os(i)] && pontdb[os(i)] == legk)
			ret[i] = 1;
	}

	return ret;
}

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