제출 #1244777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244777		RakhimovAmir	열쇠 (IOI21_keys)	C++20	100 / 100	562 ms	123180 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<int, int>>> v;
vector<vector<int>> rev;
vector<vector<int>> g;
vector<vector<int>> now;
vector<bool> used;
vector<int> ord;
vector<int> comp;
vector<int> sz;
vector<map<int, int>> color;
int n;
void dfs(int x) {
	used[x] = 1;
	for (auto to : g[x]) {
		if (used[to])
			continue;
		dfs(to);
	}
	ord.push_back(x);
}
void go(int x, int nw) {
	comp[x] = nw;
	for (auto to : rev[x]) {
		if (comp[to] != -1)
			continue;
		go(to, nw);
	} 
}
int condensate(int n) {
	rev.clear();
	rev.resize(n);
	used.resize(n);
	comp.resize(n);
	fill(used.begin(), used.end(), 0);
	fill(comp.begin(), comp.end(), -1);
	ord.clear();
	for (int i = 0; i < n; i++) {
		for (auto to : g[i]) {
			rev[to].push_back(i);
		}
	}
	for (int i = 0; i < n; i++) {
		if (!used[i]) {
			dfs(i);
		}
	}
	reverse(ord.begin(), ord.end());
	int nw = 0;
	// cout << "ord: ";
	for (auto i : ord) {
		// cout << i << " ";
		if (comp[i] == -1) {
			// cout << i << " " << nw << "go\n";
			go(i, nw);
			nw++;
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	cout << comp[i] << " ";
	// }
	// cout << "\n";
	return nw;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(r.size(), 0), p(r.size(), 0), keys(r.size());
	queue<int> q;
	n = r.size();
	::v.resize(n);
	used.resize(n);
	now.resize(n);
	g.resize(n);
	int mn = n + 1;
	// cout << n << "\n";
	for (int i = 0; i < (int)u.size(); i++) {
		// cout << u[i] << "\n";
		::v[u[i]].push_back({v[i], c[i]});
		::v[v[i]].push_back({u[i], c[i]});
	}
	for (int i = 0; i < n; i++) {
		for (auto [to, nd] : ::v[i]) {
			if (nd == r[i]) {
				g[i].push_back(to);
				// cout << "add " << i << " " << to << "\n";
			}
		}
	}
	int C = condensate(n);
	vector<int> comp0;
	sz.resize(C);
	color.resize(C);
	fill(sz.begin(), sz.end(), 0);
	g.clear();
	g.resize(C);
	for (int i = 0; i < n; i++) {
		sz[comp[i]]++;
		color[comp[i]][r[i]] = 1;
		// cout << i << " comp " << comp[i] << "\n";
	}
	for (int i = 0; i < n; i++) {
		for (auto [to, nd] : ::v[i]) {
			if (comp[to] != comp[i] && color[comp[i]][nd]) {
				// cout << "add " << comp[i] << " " << comp[to] << "\n";
				g[comp[i]].push_back(comp[to]);
			}
		}
	}
	// cout << "_____\n";
	comp0 = comp;
	int C2 = condensate(C);
	vector<int> sz2(C2, 0);
	vector<int> leaf(C2, 1);
	for (int i = 0; i < C; i++) {
		sz2[comp[i]] += sz[i];
		// cout << i << " comp " << comp[i] << "\n";
	}
	for (int i = 0; i < C; i++) {
		for (auto to : g[i]) {
			if (comp[to] != comp[i]) {
				leaf[comp[i]] = 0;
			}
		}
	}
	// cout << "mn " << mn << "\n";
	for (int i = 0; i < C2; i++) {
		// cout << i << " " << leaf[i] << " " << sz2[i] << "\n";
		if (leaf[i]) {
			mn = min(mn, sz2[i]);
		}
	}
	// cout << "mn " << mn << "\n";
	for (int i = 0; i < n; i++) {
		// cout << i << " compcomp " << leaf[comp[comp0[i]]] << " " << sz2[comp[comp0[i]]] << "\n";
		if (leaf[comp[comp0[i]]] && sz2[comp[comp0[i]]] == mn) {
			ans[i] = 1;
		}
	}
	return ans;
}

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