| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 436114 | dacin21 | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
uint64_t steps = 0;
uint64_t steps_2 = 0;
struct Edge_Compoment{
int key;
vector<int> vertices;
};
vector<Edge_Compoment> edge_components;
template<typename T>
void join(vector<T> &a, vector<T> &b){
if(a.size() < b.size()){
a.swap(b);
}
steps_2 += b.size();
a.insert(a.end(), b.begin(), b.end());
b.clear();
}
struct Component{
vector<int> vertices;
unordered_set<int> keys;
unordered_map<int, int> edge_pos;
unordered_map<int, vector<int> > reachable_edges;
unordered_map<int, vector<int> > unreachable_edges;
template<typename T>
bool search(T callback){
while(!reachable_edges.empty()){
auto it = reachable_edges.begin();
while(!it->second.empty()){
auto&p = it->second.back();
auto &pos = edge_pos[p];
auto&vv = edge_components[p].vertices;
while(pos < (int)vv.size()){
if(callback(vv[pos])) return true;
++pos;
}
it->second.pop_back();
}
reachable_edges.erase(it);
}
return false;
}
void add_key(int c){
if(!keys.count(c)){
keys.insert(c);
if(unreachable_edges.count(c)){
auto &v = reachable_edges[c];
auto &w = unreachable_edges[c];
join(v, w);
unreachable_edges.erase(c);
}
}
}
size_t size(){
return reachable_edges.size() + unreachable_edges.size() + keys.size() /*+edge_pos.size()*/;
}
void absorb(Component &o){
join(vertices, o.vertices);
for(auto &e:o.reachable_edges){
++steps;
join(reachable_edges[e.first], e.second);
}
for(auto &e:o.unreachable_edges){
++steps;
if(keys.count(e.first)){
join(reachable_edges[e.first], e.second);
} else {
join(unreachable_edges[e.first], e.second);
}
}
for(auto &e:o.keys){
++steps;
add_key(e);
}
if(edge_pos.size() < o.edge_pos.size()){
edge_pos.swap(o.edge_pos);
}
for(auto const&e:o.edge_pos){
++steps;
auto &f = edge_pos[e.first];
f = max(f, e.second);
}
}
};
struct DSU{
DSU(int n_) : n(n_), p(n, -1), comps(n){
}
int f(int x){
++steps_2;
return p[x] < 0 ? x : p[x] = f(p[x]);
}
Component& c(int x){
return comps[f(x)];
}
bool u(int a, int b){
++steps;
a = f(a);
b = f(b);
if(a == b) return false;
if(comps[a].size() < comps[b].size()){
swap(a, b);
}
comps[a].absorb(comps[b]);
p[b] = a;
return true;
}
int n;
vector<int> p;
vector<Component> comps;
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
const int m = u.size();
const int n = r.size();
map<int, vector<int> > c_inv;
for(int i=0; i<m; ++i){
c_inv[c[i]].push_back(i);
}
DSU uni(n);
// find edge components
edge_components.clear();
vector<vector<int> > g(n);
vector<int> vis(n, -1);
int tim = -1; // = index of last edge_component
vector<int> vert;
vert.reserve(n);
for(auto const&e:c_inv){
for(auto const&f:e.second){
g[u[f]].push_back(v[f]);
g[v[f]].push_back(u[f]);
}
const int t0 = tim;
auto rec = [&](auto rec, int u){
++steps;
if(vis[u] == tim) return;
vis[u] = tim;
uni.comps[u].unreachable_edges[e.first].push_back(tim);
//edge_components.back().vertices.push_back(u);
vert.push_back(u);
for(auto const&e:g[u]){
rec(rec, e);
}
};
for(auto const&f:e.second){
++steps_2;
if(vis[u[f]] <= t0){
++tim;
vert.clear();
edge_components.push_back(Edge_Compoment{e.first});
rec(rec, u[f]);
edge_components.back().vertices = vert;
}
}
for(auto const&f:e.second){
g[u[f]].pop_back();
g[v[f]].pop_back();
}
}
cerr << "tmp\n";
for(int i=0; i<n; ++i){
uni.c(i).add_key(r[i]);
uni.c(i).vertices.push_back(i);
}
cerr << "go search\n";
pair<int, vector<int> > out(n+1, {});
// run search
vis.assign(n, 0);
tim = 1;
vector<int> to(n, -1);
vector<int> prev(n, -1);
for(int i=0; i<n; ++i){
int a = uni.f(i);
++tim;
if(vis[a] == 0){
vis[a] = tim;
prev[a] = -1;
// find out edge
for(;;){
auto res = uni.comps[a].search([&](int const&v){
//cerr << " => " << v << "\n";
const int b = uni.f(v);
if(b == a) return false; // loop
if(vis[b] == 0){
//cerr << "move to: " << b << "\n";
to[a] = b;
prev[b] = a;
vis[b] = tim;
// continue search with b
a = b;
return true;
}
if(vis[b] == tim){
//cerr << "cycle " << a;
// extract cycle
int cnt = 0;
for(int c = b; c != a; c = to[c]){
//cerr << " " << c;
uni.u(a, c);
++cnt;
}
//cerr << "cycle: " << cnt << "\n";
const int aa = uni.f(a);
if(prev[b] != -1){
assert(to[prev[b]] == b);
to[prev[b]] = aa;
}
prev[aa] = prev[b];
a = aa;
//cerr << " -> " << a << "\n";
to[a] = -1;
assert(vis[a] == tim);
return true;
}
// found old vertices -> finish
//cerr << "old " << b << "\n";
a = -1;
return true;
});
if(a == -1) break; // found old vertices
if(!res){
auto const&v = uni.comps[a].vertices;
//cerr << v.size() << " : ";
//for(auto &e : v) cerr << e << " ";
//cerr << "\n";
if((int)v.size() < out.first){
out.first = v.size();
out.second.clear();
}
if((int)v.size() == out.first){
out.second.insert(out.second.end(), v.begin(), v.end());
}
break;
}
}
}
}
vector<int> ret(n);
for(auto const&e:out.second){
ret[e] = 1;
}
cerr << steps << "\n";
cerr << steps_2 << "\n";
return ret;
}