CF555E Case of Computer Network

#pragma GCC optimize(3)#include <bits/stdc++.h>using namespace std;#define down(x, y) x = min(x, y)int n, m, q;struct edge { ???int from, to, nxt, id;} edges[400005];struct edgE { ???int to, nxt;} edgEs[400005];int e0, e = 1, e2 = 1, hed[200005], hEd[200005], tim = 0, fa[200005], dfn[200005], low[200005], scc[200005], dis[200005], lca[18][200005];int flg[200005]; bool root[200005]; bool goon[200005];int leaves[200005], top=0;const int CLEAN_FLAG = 0x1;const int UP_FLAG = 0x2;const int DOWN_FLAG = 0x4;stack<int> S;inline bool hasflag(int x, int attr) { ???return flg[x] & attr;}inline bool setflag(int x, int attr) { ???if (attr == UP_FLAG && hasflag(x, DOWN_FLAG)) return false; ???if (attr == DOWN_FLAG && hasflag(x, UP_FLAG)) return false; ???flg[x] |= attr; ???return true;}inline void addedge(int x, int y) { ???edges[e] = (edge){x, y, hed[x], e2}; ???hed[x] = e++; ???edges[e] = (edge){y, x, hed[y], e2++}; ???hed[y] = e++;}inline void addedgE(int x, int y) { ???edgEs[e] = (edgE){y, hEd[x]}; ???hEd[x] = e++;}inline void _tarjan(int x) { ???dfn[x] = low[x] = ++tim; ???S.push(x); ???for (int e=hed[x]; e; e=edges[e].nxt) { ???????int y = edges[e].to; ???????if (edges[e].id == fa[x]) continue; ???????if (!dfn[y]) { ???????????fa[y] = edges[e].id; ???????????_tarjan(y); ???????????down(low[x], low[y]); ???????} else down(low[x], dfn[y]); ???} ???if (dfn[x] == low[x]) { ???????scc[x] = ++e2; ???????while (S.top() != x) { ???????????scc[S.top()] = e2; ???????????S.pop(); ???????} ???????S.pop(); ???}}inline void tarjan() { ???for (int i=1; i<=n; i++) if (!dfn[i]) _tarjan(i); ???for (int i = 0; i < e0; i++) { ???????int x = edges[i].from, y = edges[i].to; ???????if (scc[x] == scc[y]) continue; ???????addedgE(scc[x], scc[y]); ???}}inline void lca_pre() { ???for (int i=1; i<18; i++) ???????for (int j=1; j<=n; j++) ???????????lca[i][j] = lca[i-1][lca[i-1][j]];}inline int LCA(int x, int y) { ???if (dis[x] > dis[y]) swap(x, y); ???int u = dis[x], v = dis[y]; ???int X=x, Y=y; ???for (int det = v-u, i=0; det; det>>=1, ++i) ???????if (det & 1) Y = lca[i][Y]; ???if (X == Y) return X; ???for (int i=17; i>=0; i--) { ???????if (lca[i][X] == lca[i][Y]) continue; ???????X = lca[i][X]; Y = lca[i][Y]; ???} ???return lca[0][X];}int group[200005], current;inline void dfs(int x, int fa) { ???bool isleaf = true; group[x] = current; ???for (int e=hEd[x]; e; e=edgEs[e].nxt) { ???????int y = edgEs[e].to; ???????if (y != fa) { ???????????isleaf = false; ???????????lca[0][y] = x; ???????????dis[y] = dis[x] + 1; ???????????dfs(y, x); ???????} ???} ???if (isleaf) leaves[top++] = x;}inline bool akmachine(int x, int flag) { ???while (!root[x]) { ???????if (goon[x]) return true; ???????goon[x] = true; ???????if (hasflag(x, UP_FLAG) && !hasflag(x, CLEAN_FLAG) && (flag & DOWN_FLAG) ????????|| hasflag(x, DOWN_FLAG) && !hasflag(x, CLEAN_FLAG) && (flag & UP_FLAG)) ???????????return false; ???????if (hasflag(x, CLEAN_FLAG)) flag = 0; ???????flag = flg[x] & (UP_FLAG | DOWN_FLAG); ???????x = lca[0][x]; ???} ???return true;}inline bool check() { ???for (int i=0; i<top; i++) if (!akmachine(leaves[i], 0)) return false; ???return true;}inline bool solve() { ???for (int i=1; i<=n; i++) ???????if (!dis[i]) { ???????????current = i; lca[0][i] = i; root[i] = 1; ???????????dfs(i, 0); ???????} ???lca_pre(); ???while (q--) { ???????int s, t; cin >> s >> t; ???????s = scc[s]; t = scc[t]; ???????if (group[s] != group[t]) return false; ???????if (s == t) continue; ???????int p = LCA(s, t); ???????if (p != s) if (!setflag(s, UP_FLAG)) return false; ???????if (p != t) if (!setflag(t, DOWN_FLAG)) return false; ???????setflag(p, CLEAN_FLAG); ???} ???return check();}int main() { ???ios :: sync_with_stdio(false); cin.tie(0); ???cin >> n >> m >> q; ???for (int i=1; i<=m; i++) { ???????int x, y; cin >> x >> y; ???????addedge(x, y); ???} ???e0 = e; e = 1; e2 = 0; tarjan(); ???cout << (solve() ? "Yes" : "No") << endl; ???return 0;}