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;
struct node {
set<int> key;
set<pair<int,int>> adj;
set<int> adj1;
bool dead = false;
};
const int maxn = 3e5 + 5, INF = 1e9;
int n, m;
node info[maxn];
int fa[maxn];
int vis[maxn];
int rt(int u) {
if (fa[u]==u) return u;
else return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
u = rt(u); v = rt(v);
if (u==v) return;
if (info[u].key.size() + info[u].adj.size() + info[u].adj1.size() > info[v].key.size() + info[v].adj.size() + info[v].adj1.size()) swap(u, v);
for (int x:info[u].key) {
if (!info[v].key.count(x)) {
info[v].key.insert(x);
while (true) {
pair<int,int> cur = *info[v].adj.lower_bound(make_pair(x, 0));
if (cur.first!=x) break;
int V = rt(cur.second);
if (v!=V) {
info[v].adj.erase(cur);
info[v].adj1.insert(V);
}
}
}
}
for (pair<int,int> x:info[u].adj) {
if (info[v].key.count(x.first)) info[v].adj1.insert(x.second);
else info[v].adj.insert(x);
}
for (int x:info[u].adj1) info[v].adj1.insert(x);
fa[u] = v;
}
bool dfs(int u) {
bool done = true;
while (done) {
done = false;
u = rt(u);
vis[u] = 1;
int v = -1;
while (info[u].adj1.size() > 0) {
v = *info[u].adj1.begin();
if (u==rt(v)) {info[u].adj1.erase(u); v = -1;}
else {
info[u].adj1.erase(v);
v = rt(v);
break;
}
}
// cout << u << " " << v << endl;
if (v==-1) break;
if (vis[v]==2 || info[v].dead) {info[u].dead = true; return false;}
if (vis[v]==1) {merge(u, v); return true;}
if (dfs(v)) {
v = rt(v);
if (rt(u) == v) {done = true; break;}
else {merge(u, v); return true;}
} else {
u = rt(u);
info[u].dead = true;
return false;
}
}
vis[rt(u)] = 2;
return false;
}
vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
n = r.size();
for (int i=0;i<n;i++){
info[i].key.insert(r[i]);
fa[i] = i;
info[i].adj.insert({INF, INF});
}
int m = U.size();
for (int i=0;i<m;i++) {
if (r[U[i]]!=C[i]) info[U[i]].adj.insert({C[i], V[i]});
else info[U[i]].adj1.insert(V[i]);
if (r[V[i]]!=C[i]) info[V[i]].adj.insert({C[i], U[i]});
else info[V[i]].adj1.insert(U[i]);
}
for (int i=0;i<n;i++) if (!vis[rt(i)]) bool trash = dfs(i);
int sz[n];
for (int i=0;i<n;i++) sz[i] = 0;
for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
sz[rt(i)]++;
}
int mn = INF;
for (int i=0;i<n;i++) if (!info[rt(i)].dead) {
mn = min(sz[rt(i)], mn);
}
vector<int> ans(n, 0);
for (int i=0;i<n;i++) ans[i] = (!info[rt(i)].dead && sz[rt(i)]==mn);
return ans;
}
Compilation message (stderr)
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:94:49: warning: unused variable 'trash' [-Wunused-variable]
94 | for (int i=0;i<n;i++) if (!vis[rt(i)]) bool trash = dfs(i);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |