| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 795980 | MattTheNub | Keys (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.
#include <bits/stdc++.h>
using namespace std;
template <class T> using v = vector<T>;
#ifdef EVAL
#define dbg(...)
#define dbg2d(...)
#else
istream &__cin = cin;
#include "../../debug.h"
__cinwrapper __cin_wrapper;
#include "../../debug.cpp"
#endif
#include <vector>
#define f first
#define s second
using ll = long long;
using int2 = pair<int, int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {
static const int RANDOM;
static unsigned hash_f(uint64_t x) {
x += RANDOM;
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
static unsigned hash_comb(unsigned a, unsigned b) {
return hash_f(a * 31 + b);
}
int operator()(int x) const { return hash_f(x); }
int operator()(ll x) const { return hash_f(x); }
template <class T1, class T2> int operator()(pair<T1, T2> x) const {
return hash_comb((*this)(x.f), (*this)(x.s));
}
int operator()(const string &s) const {
int hash = 0;
for (char c : s) {
hash = hash_comb(c, hash);
}
return hash;
}
};
const int chash::RANDOM = rng();
template <class K, class V> using ht = gp_hash_table<K, V, chash>;
template <class T> using hs = gp_hash_table<T, null_type, chash>;
struct Edg {
int u, v, c, i;
friend bool operator<(Edg a, Edg b) {
return (a.c == b.c) ? (a.i < b.i) : (a.c < b.c);
}
};
queue<Edg> nxt;
v<int2> vis;
struct DSU {
v<int> e;
v<hs<int>> keys;
v<set<Edg>> edg;
DSU(int n) : keys(n), edg(n) { e = v<int>(n, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
if (e[x] > e[y]) {
swap(x, y);
}
e[x] += e[y];
e[y] = x;
if (edg[y].size() + keys[y].size() > edg[x].size() + keys[x].size()) {
keys[y].swap(keys[x]);
edg[y].swap(edg[x]);
}
for (auto z : keys[y]) {
auto it = edg[x].lower_bound({0, 0, z, -1});
while (it != edg[x].end() && it->c == z) {
nxt.push(*it);
it++;
edg[x].erase(prev(it));
}
keys[x].insert(z);
}
for (auto z : edg[y]) {
if (keys[x].find(z.c) != keys[x].end()) {
nxt.push(z);
} else {
edg[y].insert(z);
}
}
return true;
}
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
std::vector<int> v, std::vector<int> c) {
int n = r.size();
int m = u.size();
DSU dsu(n);
vis.assign(m, {-1, -1});
for (int i = 0; i < m; i++) {
dsu.edg[u[i]].insert({u[i], v[i], c[i], i});
dsu.edg[v[i]].insert({v[i], u[i], c[i], i});
if (r[u[i]] == c[i]) {
nxt.push({u[i], v[i], c[i], i});
}
if (r[v[i]] == c[i]) {
nxt.push({v[i], u[i], c[i], i});
}
}
for (int i = 0; i < n; i++) {
dsu.keys[i].insert(r[i]);
}
while (nxt.size()) {
Edg edg = nxt.front();
nxt.pop();
if (vis[edg.i].s != -1 || vis[edg.i].f == edg.u)
continue;
else if (vis[edg.i].f == -1) {
dbg(edg.u, edg.v);
vis[edg.i].f = edg.u;
} else {
dbg(edg.u, edg.v);
vis[edg.i].s = edg.u;
dsu.unite(edg.u, edg.v);
}
}
dbg(vis);
hs<int> components;
for (int i = 0; i < n; i++) {
components.insert(dsu.get(i));
}
for (int i = 0; i < m; i++) {
if (vis[i].s == -1 && vis[i].f != -1) {
components.erase(dsu.get(vis[i].f));
}
}
int mn = INT_MAX;
for (auto x : components) {
mn = min(mn, dsu.size(x));
}
hs<int> componentstoo;
for (auto x : components) {
if (dsu.size(x) == mn) {
componentstoo.insert(x);
}
}
vector<int> ans(n, 0);
for (int i = 0; i < n; i++) {
if (componentstoo.find(dsu.get(i)) != componentstoo.end()) {
ans[i] = 1;
}
}
return ans;
}