Submit Info #48531

Problem Lang User Status Time Memory
Dominator Tree cpp-acl (anonymous) AC 47 ms 21.68 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.70 MiB
example_01 AC 2 ms 0.68 MiB
random_00 AC 18 ms 16.62 MiB
random_01 AC 47 ms 19.69 MiB
random_02 AC 11 ms 7.43 MiB
random_03 AC 27 ms 21.68 MiB
random_04 AC 3 ms 2.52 MiB

#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,fma") typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; typedef long double db; #define MP make_pair #define PB push_back #define X first #define Y second #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i) #define ALL(a) a.begin(), a.end() #define SZ(a) (int)((a).size()) #define FILL(a, value) memset(a, value, sizeof(a)) #define debug(a) cerr << #a << " = " << a << endl; template<typename T> void setmax(T& x, T y) {x = max(x, y);} template<typename T> void setmin(T& x, T y) {x = min(x, y);} template<typename T> void print(const T& a, ostream& out){ for(auto i: a) out << i << ' '; out << endl; } const double PI = acos(-1.0); const LL INF = 1e9 + 47; const LL LINF = INF * INF; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const double EPS = 1e-7; namespace Strings{ struct SuffixArray { string s; int n; vector<int> SA,rev; SuffixArray() {} SuffixArray(const string& s_) : s(s_), n(int(s.size())) { vector<int> s2(n); for (int i = 0; i < n; i++) { s2[i] = s[i]; } SA = sa_is(s2, 255); rev.resize(n); for (int i = 0; i < n; i++) { rev[SA[i]] = i; } } int operator[](int i) const { assert(0 <= i and i < n); return SA[i]; } bool lt_substr(const string& t, int si, int ti) { int tn = int(t.size()); while(si < n && ti < tn) { if(s[si] < t[ti]) return 1; if(s[si] > t[ti]) return 0; si++; ti++; } return si == n && ti < tn; } int lower_bound(const string& t) { int l = -1, r = n; while(l + 1 < r) { int m = (l+r)>>1; if(lt_substr(t,SA[m],0)) l = m; else r = m; } return r; } int upper_bound(string& t) { t.back()++; int res=lower_bound(t); t.back()--; return res; } // O(|T|*log|S|) int count(string& t) { return upper_bound(t)-lower_bound(t); } private: vector<int> sa_naive(const vector<int>& s_) { int n_ = int(s_.size()); vector<int> sa(n_); iota(sa.begin(), sa.end(), 0); sort(sa.begin(), sa.end(), [&](int l, int r) { if (l == r) return false; while (l < n_ && r < n_) { if (s_[l] != s_[r]) return s_[l] < s_[r]; l++; r++; } return l == n_; }); return sa; } vector<int> sa_doubling(const vector<int>& s_) { int n_ = int(s_.size()); vector<int> sa(n_), rnk = s_, tmp(n_); iota(sa.begin(), sa.end(), 0); for (int k = 1; k < n_; k *= 2) { auto cmp = [&](int x, int y) { if (rnk[x] != rnk[y]) return rnk[x] < rnk[y]; int rx = x + k < n_ ? rnk[x + k] : -1; int ry = y + k < n_ ? rnk[y + k] : -1; return rx < ry; }; sort(sa.begin(), sa.end(), cmp); tmp[sa[0]] = 0; for (int i = 1; i < n_; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0); } swap(tmp, rnk); } return sa; } template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40> vector<int> sa_is(const vector<int>& s_, int upper) { int n_ = int(s_.size()); if (n_ == 0) return {}; if (n_ == 1) return {0}; if (n_ == 2) { if (s_[0] < s_[1]) { return {0, 1}; } else { return {1, 0}; } } if (n_ < THRESHOLD_NAIVE) { return sa_naive(s_); } if (n_ < THRESHOLD_DOUBLING) { return sa_doubling(s_); } vector<int> sa(n_); vector<bool> ls(n_); for (int i = n_ - 2; i >= 0; i--) { ls[i] = (s_[i] == s_[i + 1]) ? ls[i + 1] : (s_[i] < s_[i + 1]); } vector<int> sum_l(upper + 1), sum_s(upper + 1); for (int i = 0; i < n_; i++) { if (!ls[i]) { sum_s[s_[i]]++; } else { sum_l[s_[i] + 1]++; } } for (int i = 0; i <= upper; i++) { sum_s[i] += sum_l[i]; if (i < upper) sum_l[i + 1] += sum_s[i]; } auto induce = [&](const vector<int>& lms) { fill(sa.begin(), sa.end(), -1); vector<int> buf(upper + 1); copy(sum_s.begin(), sum_s.end(), buf.begin()); for (auto d : lms) { if (d == n_) continue; sa[buf[s_[d]]++] = d; } copy(sum_l.begin(), sum_l.end(), buf.begin()); sa[buf[s_[n_ - 1]]++] = n_ - 1; for (int i = 0; i < n_; i++) { int v = sa[i]; if (v >= 1 && !ls[v - 1]) { sa[buf[s_[v - 1]]++] = v - 1; } } copy(sum_l.begin(), sum_l.end(), buf.begin()); for (int i = n_ - 1; i >= 0; i--) { int v = sa[i]; if (v >= 1 && ls[v - 1]) { sa[--buf[s_[v - 1] + 1]] = v - 1; } } }; vector<int> lms_map(n_ + 1, -1); int m = 0; for (int i = 1; i < n_; i++) { if (!ls[i - 1] && ls[i]) { lms_map[i] = m++; } } vector<int> lms; lms.reserve(m); for (int i = 1; i < n_; i++) { if (!ls[i - 1] && ls[i]) { lms.push_back(i); } } induce(lms); if (m) { vector<int> sorted_lms; sorted_lms.reserve(m); for (int v : sa) { if (lms_map[v] != -1) sorted_lms.push_back(v); } vector<int> rec_s(m); int rec_upper = 0; rec_s[lms_map[sorted_lms[0]]] = 0; for (int i = 1; i < m; i++) { int l = sorted_lms[i - 1], r = sorted_lms[i]; int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n_; int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n_; bool same = true; if (end_l - l != end_r - r) { same = false; } else { while (l < end_l) { if (s_[l] != s_[r]) { break; } l++; r++; } if (l == n_ || s_[l] != s_[r]) same = false; } if (!same) rec_upper++; rec_s[lms_map[sorted_lms[i]]] = rec_upper; } auto rec_sa = sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper); for (int i = 0; i < m; i++) { sorted_lms[i] = lms[rec_sa[i]]; } induce(sorted_lms); } return sa; } }; struct LongestCommonPrefix { SuffixArray sa; vector<int> ht; vector<vector<int>> node; LongestCommonPrefix(const string& S) : sa(S) { int n = SZ(S); assert(n >= 1); vector<int> lcp(n-1); int h = 0; for (int i = 0; i < n; i++) { if (h > 0) h--; if (sa.rev[i] == 0) continue; int j = sa[sa.rev[i] - 1]; for (; j + h < n && i + h < n; h++) { if (S[j + h] != S[i + h]) break; } lcp[sa.rev[i] - 1] = h; } h = 1; while ((1<<h) <= n-1) h++; node.assign(h, vector<int>(n-1,0)); ht.assign((1<<h)+1,0); for (int j = 2; j < (1<<h)+1; j++) ht[j] = ht[j>>1] + 1; for (int j = 0; j < n-1; j++) node[0][j] = lcp[j]; for (int i = 1; i < h; i++) { int s = 1 << i; for (int j = 0; j < n-1; j += s<<1) { int t = min(j+s, n-1); node[i][t-1] = lcp[t-1]; for (int k = t-2; k >= j; k--) node[i][k] = min(lcp[k],node[i][k+1]); if (n-1 <= t) break; node[i][t] = lcp[t]; int r = min(t+s,n-1); for (int k = t+1; k < r; k++) node[i][k] = min(node[i][k-1],lcp[k]); } } } // a, b are indices for suffix array int query(int a, int b) { assert(a != b); if(a > b) swap(a,b); if(a >= --b) return node[0][a]; return min(node[ht[a^b]][a],node[ht[a^b]][b]); } // a, b are indices for string int get_lcp(int a, int b) { return query(sa.rev[a],sa.rev[b]); } }; namespace Automat{ const int MAX = 1 << 19; struct node{ int g[26]; int link, len; void init(){ FILL(g, -1); link = len = -1; } }; struct automaton{ node A[MAX * 2]; int sz, head; void init(){ sz = 1; head = 0; A[0].init(); } void add(char x){ int ch = x - 'a'; int nhead = sz++; A[nhead].init(); A[nhead].len = A[head].len + 1; int cur = head; head = nhead; while(cur != -1 && A[cur].g[ch] == -1) { A[cur].g[ch] = head; cur = A[cur].link; } if(cur == -1) { A[head].link = 0; return; } int p = A[cur].g[ch]; if(A[p].len == A[cur].len + 1) { A[head].link = p; return; } int q = sz++; A[q] = A[p]; A[q].len = A[cur].len + 1; A[p].link = A[head].link = q; while(cur != -1 && A[cur].g[ch] == p) { A[cur].g[ch] = q; cur = A[cur].link; } } }; }; namespace Z_func{ template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) { int n = int(s.size()); if (n == 0) return {}; std::vector<int> z(n); z[0] = 0; for (int i = 1, j = 0; i < n; i++) { int& k = z[i]; k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]); while (i + k < n && s[k] == s[i + k]) k++; if (j + z[j] < i + z[i]) j = i; } z[0] = n; return z; } std::vector<int> z_algorithm(const std::string& s) { int n = int(s.size()); std::vector<int> s2(n); for (int i = 0; i < n; i++) { s2[i] = s[i]; } return z_algorithm(s2); } } namespace P_func{ template <class T> std::vector<int> p_algorithm(const std::vector<T>& s) { int n = SZ(s); if (n == 0) return {}; vector<int> pi (n); for (int i = 1; i < n; ++i) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) ++j; pi[i] = j; } return pi; } std::vector<int> p_algorithm(const std::string& s) { int n = int(s.size()); std::vector<int> s2(n); for (int i = 0; i < n; i++) { s2[i] = s[i]; } return p_algorithm(s2); } } namespace Aho_Corasick{ const int MAX = 1 << 17; const int AL = 30; struct node{ int p; int c; int g[AL]; int nxt[AL]; int link; void init(){ c = -1; p = -1; FILL(g,-1); FILL(nxt,-1); link = -1; } }; struct AC{ node A[MAX]; int sz; void init(){ A[0].init(); sz = 1; } int AddStr(string & s) {//returns vertex number for string int x = 0; FOR(i, 0, SZ(s)){ int c = s[i] - 'a'; if(A[x].nxt[c] == -1){ A[x].nxt[c] = sz; A[sz].init(); A[sz].c = c; A[sz].p = x; sz++; } x = A[x].nxt[c]; } return x; } int go(int x, int c){ if(A[x].g[c] == -1) { if(A[x].nxt[c] != -1) A[x].g[c] = A[x].nxt[c]; else if (x != 0) A[x].g[c] = go(getLink(x), c); else A[x].g[c] = 0; } return A[x].g[c]; } int getLink(int x){ if(A[x].link == -1) { if(x == 0 || A[x].p == 0) return 0; A[x].link = go(getLink(A[x].p), A[x].c); } return A[x].link; } }; }; struct Manacher { vector<int> p[2]; // i | i + 1 -> p[0][i + 1] // i -> p[1][i] Manacher(const string &s) { int n = s.size(); p[0].resize(n+1); p[1].resize(n); for (int z=0; z<2; z++) for (int i=0, l=0, r=0; i<n; i++) { int t = r-i+!z; if (i<r) p[z][i] = min(t, p[z][l+t]); int L = i-p[z][i], R = i+p[z][i]-!z; while (L>=1 && R+1<n && s[L-1] == s[R+1]) p[z][i]++, L--, R++; if (R>r) l=L, r=R; } } bool ispalin(int l, int r) { int mid = (l+r+1)/2, sz = r-l+1; return 2*p[sz%2][mid]+sz%2 >= sz; } }; }; using namespace Strings; struct DominatorTree { vector<basic_string<int>> g, rg, bucket; vector<int> arr, par, rev, sdom, dom, dsu, label; int n, t; DominatorTree(int n) : g(n), rg(n), bucket(n), arr(n, -1), par(n), rev(n), sdom(n), dom(n), dsu(n), label(n), n(n), t(0) {} void add_edge(int u, int v) { g[u] += v; } void dfs(int u) { arr[u] = t; rev[t] = u; label[t] = sdom[t] = dsu[t] = t; t++; for (int w : g[u]) { if (arr[w] == -1) { dfs(w); par[arr[w]] = arr[u]; } rg[arr[w]] += arr[u]; } } int find(int u, int x = 0) { if (u == dsu[u]) return x ? -1 : u; int v = find(dsu[u], x+1); if (v < 0) return u; if (sdom[label[dsu[u]]] < sdom[label[u]]) label[u] = label[dsu[u]]; dsu[u] = v; return x ? v : label[u]; } vector<int> run(int root) { dfs(root); iota(dom.begin(), dom.end(), 0); for (int i=t-1; i>=0; i--) { for (int w : rg[i]) sdom[i] = min(sdom[i], sdom[find(w)]); if (i) bucket[sdom[i]] += i; for (int w : bucket[i]) { int v = find(w); if (sdom[v] == sdom[w]) dom[w] = sdom[w]; else dom[w] = v; } if (i > 1) dsu[i] = par[i]; } for (int i=1; i<t; i++) { if (dom[i] != sdom[i]) dom[i] = dom[dom[i]]; } vector<int> outside_dom(n); iota(begin(outside_dom), end(outside_dom), 0); for (int i=0; i<t; i++) outside_dom[rev[i]] = rev[dom[i]]; return outside_dom; } }; int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); //test Automat int n, m, s; cin >> n >> m >> s; DominatorTree T(n); FOR(i, 0, m) { int a, b; cin >> a >> b; T.add_edge(a, b); } auto res = T.run(s); FOR(i, 0, n) { if(res[i] == i && i != s) res[i] = -1; cout << res[i] << " "; } cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl; return 0; }