fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_N = 2e5 + 5;
  6.  
  7. int n, m, numEdge, numRoot;
  8. vector<int> adj[MAX_N], g[MAX_N];
  9. bool deleted[MAX_N];
  10. int root[MAX_N];
  11. int timeIn[MAX_N], low[MAX_N];
  12. int dfsTime;
  13. bool mark[MAX_N];
  14. stack<int> st;
  15.  
  16. void addEdge(int u, bool t1, int v, bool t2) {
  17.     adj[u + (!t1 ? 0 : n)].push_back(v + (t2 ? 0 : n));
  18.     adj[v + (!t2 ? 0 : n)].push_back(u + (t1 ? 0 : n));
  19. }
  20.  
  21. void dfs(int u) {
  22.     timeIn[u] = low[u] = ++dfsTime;
  23.     st.push(u);
  24.  
  25.     for (int v : adj[u]) {
  26.         if (deleted[v]) continue;
  27.         if (!timeIn[v]) {
  28.             dfs(v);
  29.             low[u] = min(low[u], low[v]);
  30.         }
  31.         else {
  32.             low[u] = min(low[u], timeIn[v]);
  33.         }
  34.     }
  35.  
  36.     if (timeIn[u] == low[u]) {
  37.         ++numRoot;
  38.         int v;
  39.         do {
  40.             v = st.top();
  41.             st.pop();
  42.             deleted[v] = true;
  43.             root[v] = numRoot;
  44.         }
  45.         while (v != u);
  46.     }
  47. }
  48.  
  49. vector<int> topo;
  50. int id[MAX_N];
  51. void topoSort(int u) {
  52.     deleted[u] = true;
  53.     for (int v : g[u]) {
  54.         if (!deleted[v]) {
  55.             topoSort(v);
  56.         }
  57.     }
  58.     topo.push_back(u);
  59. }
  60.  
  61. signed main() {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(nullptr);
  64.  
  65.     cin >> n >> m;
  66.     for (int i = 1; i <= m; i++) {
  67.         int a, b, c;
  68.         bool x, y, z;
  69.         cin >> a >> x >> b >> y >> c >> z;
  70.         addEdge(a, x, b, y);
  71.         addEdge(a, x, c, z);
  72.         addEdge(b, y, c, z);
  73.     }
  74.  
  75.     for (int i = 1; i <= (n << 1); i++) {
  76.         if (!timeIn[i]) {
  77.             dfs(i);
  78.         }
  79.     }
  80.  
  81.     for (int i = 1; i <= (n << 1); i++) {
  82.         for (int v : adj[i]) {
  83.             if (root[v] != root[i]) {
  84.                 g[root[i]].push_back(root[v]);
  85.             }
  86.         }
  87.     }
  88.  
  89.     for (int i = 1; i <= numRoot; i++) {
  90.         deleted[i] = 0;
  91.     }
  92.     for (int i = 1; i <= numRoot; i++) {
  93.         if (!deleted[i]) {
  94.             topoSort(i);
  95.         }
  96.     }
  97.  
  98.     reverse(topo.begin(), topo.end());
  99.  
  100.     for (int i = 0; i < (int) topo.size(); i++) {
  101.         id[topo[i]] = i + 1;
  102.     }
  103.  
  104.     for (int i = 1; i <= n; i++) {
  105.         if (id[root[i]] == id[root[i + n]]) {
  106.             cout << -1;
  107.             return 0;
  108.         }
  109.  
  110.         mark[i] = (id[root[i]] > id[root[i + n]]);
  111.     }
  112.  
  113.     for (int i = 1; i <= n; i++) {
  114.         cout << mark[i];
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
  120.  
  121. // by Asamai
Success #stdin #stdout 0.01s 15848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mpPr5L
language:
C++14 (gcc 8.3)
created:
148 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!