This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
typedef long long LL;
typedef pair<int,int> pii;
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define REP(n) for (int __=n;__--;)
#define REP1(i,n) for (int i=1;i<=n;++i)
#define REP0(i,n) for (int i=0;i<n;++i)
typedef vector <int> vi;
#include "keys.h"
const int maxn = 3e5 + 200;
vector <vector <int>> adj,inv;
set <int> dag[maxn];
stack <int> ts;
bool vis[maxn];
void dfs1(int x){
vis[x] = true;
for (auto i:adj[x]) if (!vis[i]) dfs1(i);
ts.push(x);
}
int bl[maxn],siz[maxn],dp[maxn],indeg[maxn];
void dfs2(int x,int b){
vis[x] = true;
bl[x] = b;
++siz[b];
for (auto i:inv[x]) if (!vis[i]) dfs2(i,b);
}
void dfs3(int x){
dp[x] += siz[x];
for (auto i:dag[x]){
dp[i] += dp[x];
if (!(--indeg[i])) dfs3(i);
}
}
vi find_reachable(vi r,vi u,vi v,vi c){
int n = r.size(),m = c.size();
adj.resize(n);
inv.resize(n);
vector <pii> fr(n);
REP0(i,m){
if (c[i] == r[u[i]]){
adj[u[i]].pb(v[i]);
inv[v[i]].pb(u[i]);
}
if (c[i] == r[v[i]]){
adj[v[i]].pb(u[i]);
inv[u[i]].pb(v[i]);
}
}
REP0(i,n) if (!vis[i]) dfs1(i);
REP0(i,n) vis[i] = false;
int scc = 0;
for (;!ts.empty();ts.pop()){
if (!vis[ts.top()]) dfs2(ts.top(),++scc);
}
REP0(i,n) for (auto j:adj[i]) if (bl[i] != bl[j]) dag[bl[j]].insert(bl[i]);//,cout << i << ' ' << j << '\n';
vector <int> todfs;
REP1(i,scc) for (auto j:dag[i]) ++indeg[j];
REP1(i,scc) if (!indeg[i]) todfs.pb(i);
for (auto i:todfs) dfs3(i);
vector <int> ret(n,0);
int mn = n;
REP1(i,scc) mn = min(mn,dp[i]);
REP0(i,n) if (dp[bl[i]] == mn) ret[i] = true;
return ret;
}
# | 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... |