| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 470694 | Tentacleslave | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int increment, size;
vector<int> scc_value;
vector<int> mutex;
int dfs(int v, const vector<int>& vertex, const vector<vector<pair<int, int>>>& edge_table) {
if(mutex[v] == 1)
return scc_value[v];
if(mutex[v] == 2)
return -1;
mutex[v] = 1;
int min = increment;
scc_value[v] = min;
increment++;
for(auto i : edge_table[v]) {
if(vertex[v] != i.second) continue;
int fetch = dfs(i.first, vertex, edge_table);
if(min > fetch && fetch != -1)
min = fetch;
}
scc_value[v] = min;
mutex[v] = 2;
return min;
}
vector<int> find_components(const vector<int>& vertex, const vector<vector<pair<int, int>>>& edge_table) {
increment = 0;
scc_value.resize(vertex.size());
mutex.resize(vertex.size());
fill (scc_value.begin(), scc_value.end(), 0);
fill (mutex.begin(), mutex.end(), 0);
for(vector<int>::const_iterator i = vertex.begin(); i != vertex.end(); i++)
dfs(i - vertex.begin(), vertex, edge_table);
return scc_value;
}
// vertex weighted by (key, list of subvertex), edge weighted by (connector's key id)
vector<int> find_reachable_internal(vector<pair<int, vector<int>>> vertex, vector<vector<pair<int, int>>> edge_table) {
vector<int> simple_vertex;
for(auto i : vertex)
simple_vertex.push_back(i.first);
vector<int> scc_table = find_components(simple_vertex, edge_table);
// To-do: construct new graph consists of SCC
// Required: mapping vertex to SCC number ... vertex (--- scc_table --->) (--- scc_map --->) new_vertex
// Do not fetch: for all SCC, size = 1
vector<int> reverse_map = scc_table;
std::sort(reverse_map.begin(), reverse_map.end());
reverse_map.erase(unique(reverse_map.begin(), reverse_map.end()), reverse_map.end());
if(reverse_map.size() == vertex.size()) {
int min_size = 1e9;
for(auto i : vertex) {
bool res = false;
for(auto j : edge_table[i.first]) {
if(i.first == j.second)
res = true;
}
if(res) i.second.clear();
if(min_size > i.second.size() && i.second.size() > 0)
min_size = i.second.size();
}
vector<int> restored_vertex;
restored_vertex.resize(size, 0);
for(auto i : vertex) {
for(auto j : i.second) {
if(i.second.size() == min_size)
restored_vertex[j] = 0;
else
restored_vertex[j] = 1;
}
}
return restored_vertex;
}
// To-do: Query
vector<int> scc_map;
scc_map.resize(vertex.size(), 0);
for(vector<int>::iterator i = reverse_map.begin(); i != reverse_map.end(); i++)
scc_map[*i] = i - reverse_map.begin();
vector<pair<int, vector<int>>> new_vertex;
new_vertex.resize(reverse_map.size(), {0, {}});
for(auto i = new_vertex.begin(); i != new_vertex.end(); i++) {
i->first = i - new_vertex.begin();
}
for(vector<pair<int, vector<int>>>::const_iterator i = vertex.begin(); i != vertex.end(); i++) {
int pos = i - vertex.begin();
for(auto j : i->second)
new_vertex[scc_map[scc_table[pos]]].second.push_back(j);
}
vector<vector<pair<int, int>>> new_edge_table;
new_edge_table.resize(reverse_map.size(), {});
for(vector<vector<pair<int, int>>>::const_iterator i = edge_table.begin(); i != edge_table.end(); i++) {
int arg1 = scc_map[scc_table[i - edge_table.begin()]];
for(auto j : *i) {
int arg2 = scc_map[scc_table[j.first]];
int arg3 = scc_map[scc_table[j.second]];
new_edge_table[arg1].push_back({arg2, arg3});
}
}
return find_reachable_internal(new_vertex, new_edge_table);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
size = r.size();
int edge_size = u.size();
vector<pair<int, vector<int>>> vertex;
vector<vector<pair<int, int>>> edge_table;
for(int i = 0; i < size; i++) {
vertex.push_back({r[i], {i}});
}
edge_table.resize(vertex.size(), {});
for(auto i = u.begin(), j = v.begin(), k = c.begin(); i != u.end() && j != v.end() && k != c.end(); i++, j++, k++) {
edge_table[*i].push_back({*j, *k});
edge_table[*j].push_back({*i, *k});
}
return find_reachable_internal(vertex, edge_table);
}