Submission #481540

#TimeUsernameProblemLanguageResultExecution timeMemory
481540yungyaoKeys (IOI21_keys)C++17
9 / 100
291 ms75000 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...