This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#if !defined(ONLINE_JUDGE) && !defined(LOCAL)
// oj.uz
#include "keys.h"
#endif
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif
using namespace std;
using pii = pair<int, int>;
int constexpr MM = 3e5+5;
int n, m;
vector<int> r;
vector<int> adj[MM];
// vector<int> adj2[MM];
int outdeg[MM];
int dfn[MM], low[MM], t, id[MM];
bool ins[MM];
stack<int> stk;
vector<int> scc[MM];
set<int> newkeys[MM], donekeys[MM];
map<int, vector<int>> to[MM];
// which weakly connected component
// this is different from id[], which is scc "root"
int par[MM];
int find(int x){
while(x != par[x])
x = par[x], par[x] = par[par[x]];
return x;
}
void merge(int a, int b){
// merges b into a
if(size(newkeys[b]) > size(newkeys[a]))
swap(newkeys[a], newkeys[b]);
for(auto i: newkeys[b])
newkeys[a].insert(i);
if(size(donekeys[b]) > size(donekeys[a]))
swap(donekeys[a], donekeys[b]);
for(auto i: donekeys[b])
donekeys[a].insert(i);
if(size(to[a]) > size(to[b]))
swap(to[a], to[b]);
for(auto &[i, v]: to[b]){
to[a][i].insert(to[a][i].end(), all(v));
}
if(size(scc[a]) > size(scc[b]))
swap(scc[a], scc[b]);
scc[a].insert(scc[a].end(), all(scc[b]));
par[find(b)] = find(a);
}
void dfs(int cur){
dfn[cur] = low[cur] = ++t;
stk.push(cur);
ins[cur] = 1;
for(auto u: adj[cur]){
if(!dfn[u]){
dfs(u);
low[cur] = min(low[cur], low[u]);
}
else if(ins[u])
low[cur] = min(low[cur], dfn[u]);
}
if(dfn[cur] == low[cur]){
int u = -1;
while(u != cur){
u = stk.top(); stk.pop();
ins[u] = 0;
id[u] = cur;
merge(cur, u);
}
}
}
vector<int> find_reachable(vector<int> _r, vector<int> a, vector<int> b, vector<int> c){
r = move(_r);
n = size(r);
m = size(a);
vector<int> res(n);
for(int i = 0; i < m; i++){
if(c[i] == r[a[i]]){
adj[a[i]].emplace_back(b[i]);
// pr("edge", a[i], b[i]);
}
else{
to[a[i]][c[i]].emplace_back(b[i]);
}
if(c[i] == r[b[i]]){
adj[b[i]].emplace_back(a[i]);
// pr("edge", a[i], b[i]);
}
else{
to[b[i]][c[i]].emplace_back(a[i]);
}
}
for(int i = 0; i < n; i++){
par[i] = i;
newkeys[i].insert(r[i]);
scc[i].emplace_back(i);
}
for(int i = 0; i < n; i++){
if(!dfn[i]){
dfs(i);
}
}
for(int i = 0; i < n; i++){
for(int j: adj[i]){
if(id[i] != id[j]){
// adj2[id[i]].emplace_back(id[j]);
outdeg[id[i]] = 1;
}
}
}
// each scc root...
vector<int> roots;
for(int i = 0; i < n; i++){
// if(!size(adj2[i])){
if(!outdeg[i]){
roots.emplace_back(i);
pr("add rt", i);
}
}
for(auto rt: roots){
while(size(newkeys[rt])){
auto i = *newkeys[rt].begin();
newkeys[rt].erase(i);
if(donekeys[rt].count(i)) continue;
donekeys[rt].insert(i);
for(auto u: to[rt][i]){
if(find(u) == find(rt)){
merge(rt, u);
}
else{
merge(u, rt);
break;
}
}
}
}
int ans = 1e9;
for(auto rt : roots){
if(find(rt) == rt){
int s = size(scc[rt]);
pr("check sz", rt, s);
if(s < ans){
ans = s;
}
}
}
for(auto rt : roots){
if(find(rt) == rt){
int s = size(scc[rt]);
if(s == ans){
pr("scc", rt);
for(auto j: scc[rt]){
pr("j", j);
res[j] = 1;
}
}
}
}
return res;
}
#ifdef LOCAL
namespace me{
void go(){
int n, m;
cin>>n>>m;
vector<int> r(n), a(m), b(m), c(m);
for(int i = 0; i < n; i++)
cin>>r[i];
for(int i = 0; i < m; i++){
cin>>a[i]>>b[i]>>c[i];
}
auto res = find_reachable(r, a, b, c);
for(int i = 0; i < size(res); i++)
cout<<res[i]<<' ';
}
}
int main(){
me::go();
}
#endif
# | 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... |