fork download
copy 
  1. /*
  2.  * Language: Standard C++23 [-std=c++23]
  3.  * Author: Zang Vũ aka zvwgvx
  4.  * Github & Discord & Facebook: @zvwgvx
  5.  */
  6.  
  7. #pragma GCC optimize("fast-math,O3")
  8. #pragma GCC optimize("no-stack-protector") 
  9. #pragma GCC optimize("unroll-loops")
  10. // #pragma GCC optimize("Ofast")
  11. // #pragma GCC target("tune=native")
  12. // #pragma GCC target("avx,avx2,fma")
  13.  
  14. #include <bits/stdc++.h>
  15.  
  16. using namespace std;
  17.  
  18. #define ENV defined(LOCAL)
  19. #define el cout << '\n'
  20. #define rt return
  21. #define ll long long
  22. #define ull unsigned ll
  23. #define pii pair <int, int>
  24. #define pll pair <ll, ll>
  25. #define v vector
  26. #define vi v <int>
  27. #define vl v <ll>
  28. #define vc v <char>
  29. #define vvi v <v <int>>
  30. #define vvl v <v <ll>>
  31. #define mts multiset
  32. #define mtm multimap
  33. #define ump unordered_map
  34. #define ust unordered_set
  35. #define umts unordered_multiset
  36. #define umtm unordered_multimap
  37. #define priq priority_queue
  38.  
  39. template <typename T>
  40. T fgcd(T a, T b) {
  41.     if (!a || !b) rt a | b;
  42.     unsigned shift = __builtin_ctzll(a | b);
  43.     a >>= __builtin_ctzll(a);
  44.     while (b) {
  45.         b >>= __builtin_ctzll(b);
  46.         if (a > b) swap(a, b);
  47.         b -= a;
  48.     }
  49.     rt a << shift;
  50. }
  51.  
  52. template <typename T>
  53. T fpow(T base, T exp, T mod) {
  54.     T res = 1;
  55.     for (; exp; exp >>= 1, base = base * base % mod)
  56.         if (exp & 1) res = res * base % mod;
  57.     rt res;
  58. }
  59.  
  60. template <typename T> T lcm(T a, T b) { rt a * (b / fgcd(a, b)); }
  61. template <typename T> void maximize(T& a, T b) { if (a < b) a = b; }
  62. template <typename T> void minimize(T& a, T b) { if (a > b) a = b; }
  63. template <typename T> double lg(T a, T b) { rt log(b) / log(a); }
  64. template <typename T> ull P(T n, T k) { ull res = 1; for (int i = 0; i < k; ++i) res *= (n - i); rt res; }
  65. template <typename T> ull C(T n, T k) { ull res = 1; for (int i = 1; i <= k; ++i) res = res * (n - i + 1) / i; rt res; }
  66.  
  67. const int MOD = 1e9 + 7;
  68. const int INF = 1e9;
  69. const int LIMIT = 1e6 + 5;
  70.  
  71. #if ENV
  72. void open(const string& file) {
  73.     freopen((file + ".inp").c_str(), "r", stdin);
  74.     freopen((file + ".out").c_str(), "w", stdout);
  75. }
  76. auto start = clock();
  77. void time() { cout << "\n\n[rt] " << 1.0 * (clock() - start) / CLOCKS_PER_SEC; }
  78. #endif
  79.  
  80. struct Query {
  81.     int type, x, y, k, u, v, cx, cy;
  82. };
  83.  
  84. inline int idx(int var, int val) {
  85.     rt 2 * var + val;
  86. }
  87.  
  88. void add_e(vvi& graph, const Query& q) {
  89.     int literal = idx(q.cx, q.k);
  90.     int notl = idx(q.cx, 1 - q.k);
  91.     graph[notl].push_back(literal);
  92. }
  93.  
  94. void add_e2(vvi& graph, const Query& q) {
  95.     int a = q.cx, b = q.cy;
  96.     if(q.k == 0) {
  97.         graph[idx(a, 0)].push_back(idx(b, 0));
  98.         graph[idx(b, 0)].push_back(idx(a, 0));
  99.         graph[idx(a, 1)].push_back(idx(b, 1));
  100.         graph[idx(b, 1)].push_back(idx(a, 1));
  101.     } else {
  102.         graph[idx(a, 0)].push_back(idx(b, 1));
  103.         graph[idx(b, 0)].push_back(idx(a, 1));
  104.         graph[idx(a, 1)].push_back(idx(b, 0));
  105.         graph[idx(b, 1)].push_back(idx(a, 0));
  106.     }
  107. }
  108.  
  109. void add_e3(vvi& graph, const Query& q) {
  110.     int idx_a = idx(q.cx, q.u);
  111.     int idx_b = idx(q.cy, q.v);
  112.     int notA = idx(q.cx, 1 - q.u);
  113.     int notB = idx(q.cy, 1 - q.v);
  114.     graph[notA].push_back(idx_b);
  115.     graph[notB].push_back(idx_a);
  116. }
  117.  
  118. vi findtopo(const vvi& graph) {
  119.     int nodes = graph.size();
  120.     vi order;
  121.     vector<bool> visited(nodes, false);
  122.     order.reserve(nodes);
  123.  
  124.     for (int i = 0; i < nodes; ++i) {
  125.         if (!visited[i]) {
  126.             stack<pii> que;
  127.             que.push({i, 0});
  128.             visited[i] = true;
  129.             while(!que.empty()) {
  130.                 auto &top = que.top();
  131.                 int v = top.first;
  132.                 int &it = top.second;
  133.                 if(it < (int)graph[v].size()) {
  134.                     int w = graph[v][it++];
  135.                     if(!visited[w]) {
  136.                         visited[w] = true;
  137.                         que.push({w, 0});
  138.                     }
  139.                 } else {
  140.                     order.push_back(v);
  141.                     que.pop();
  142.                 }
  143.             }
  144.         }
  145.     }
  146.     rt order;
  147. }
  148.  
  149. vi finds(const vvi& graph, const vi& order) {
  150.     int nodes = graph.size();
  151.     vvi rgraph(nodes);
  152.     for (int v = 0; v < nodes; v++) {
  153.         for (int w : graph[v]) {
  154.             rgraph[w].push_back(v);
  155.         }
  156.     }
  157.  
  158.     vi comp(nodes, -1);
  159.     int id = 0;
  160.     for (int i = nodes - 1; i >= 0; i--) {
  161.         int v = order[i];
  162.         if(comp[v] == -1) {
  163.             stack<int> st;
  164.             st.push(v);
  165.             comp[v] = id;
  166.             while(!st.empty()) {
  167.                 int cur = st.top();
  168.                 st.pop();
  169.                 for (int nxt : rgraph[cur]) {
  170.                     if(comp[nxt] == -1) {
  171.                         comp[nxt] = id;
  172.                         st.push(nxt);
  173.                     }
  174.                 }
  175.             }
  176.             id++;
  177.         }
  178.     }
  179.     rt comp;
  180. }
  181.  
  182. bool valid(const v<Query>& queries, int mid, int m) {
  183.     int nodes = 2 * m;
  184.     vvi graph(nodes);
  185.  
  186.     for (int i = 0; i < mid; ++i) {
  187.         const Query &q = queries[i];
  188.         if(q.type == 1) add_e(graph, q);
  189.         else if(q.type == 2) add_e2(graph, q);
  190.         else if(q.type == 3) add_e3(graph, q);
  191.     }
  192.  
  193.     vi order = findtopo(graph);
  194.     vi comp = finds(graph, order);
  195.  
  196.     for (int i = 0; i < m; ++i) {
  197.         if(comp[idx(i,0)] == comp[idx(i,1)])
  198.             rt 0;
  199.     }
  200.     rt 1;
  201. }
  202.  
  203. signed main() { 
  204.     cin.tie(nullptr), cout.tie(nullptr)
  205.     -> ios_base::sync_with_stdio(false);
  206.  
  207.     #if ENV 
  208.         open("main");
  209.         srand(time(nullptr));
  210.     #endif
  211.  
  212.     int t;
  213.     cin >> t;
  214.     while(t--){
  215.         int n, q;
  216.         cin >> n >> q;
  217.         vector<Query> queries(q);
  218.         vi ids;
  219.         ids.reserve(2*q);
  220.  
  221.         for (int i = 0; i < q; ++i){
  222.             int typ;
  223.             cin >> typ;
  224.             queries[i].type = typ;
  225.             if(typ == 1){
  226.                 cin >> queries[i].x >> queries[i].k;
  227.                 ids.push_back(queries[i].x);
  228.             } else if(typ == 2){
  229.                 cin >> queries[i].x >> queries[i].y >> queries[i].k;
  230.                 ids.push_back(queries[i].x);
  231.                 ids.push_back(queries[i].y);
  232.             } else if(typ == 3){
  233.                 cin >> queries[i].x >> queries[i].u >> queries[i].y >> queries[i].v;
  234.                 ids.push_back(queries[i].x);
  235.                 ids.push_back(queries[i].y);
  236.             }
  237.         }
  238.  
  239.         sort(ids.begin(), ids.end());
  240.         ids.erase(unique(ids.begin(), ids.end()), ids.end());
  241.         int m = ids.size(); 
  242.  
  243.  
  244.         for (int i = 0; i < q; ++i){
  245.             if(queries[i].type == 1){
  246.                 int pos = int(lower_bound(ids.begin(), ids.end(), queries[i].x) - ids.begin());
  247.                 queries[i].cx = pos;
  248.             } else if(queries[i].type == 2){
  249.  
  250.                 int pos1 = int(lower_bound(ids.begin(), ids.end(), queries[i].x) - ids.begin());
  251.                 int pos2 = int(lower_bound(ids.begin(), ids.end(), queries[i].y) - ids.begin());
  252.                 queries[i].cx = pos1;
  253.                 queries[i].cy = pos2;
  254.  
  255.             } else if(queries[i].type == 3){
  256.  
  257.                 int pos1 = int(lower_bound(ids.begin(), ids.end(), queries[i].x) - ids.begin());
  258.                 int pos2 = int(lower_bound(ids.begin(), ids.end(), queries[i].y) - ids.begin());
  259.                 queries[i].cx = pos1;
  260.                 queries[i].cy = pos2;
  261.  
  262.             }
  263.         }
  264.  
  265.         int left = 1, right = q + 1; 
  266.         while (left < right){
  267.             int mid = left + (right - left) / 2;
  268.             if (valid(queries, mid, m)) left = mid + 1; 
  269.             else right = mid; 
  270.         }
  271.  
  272.         if (left > q) cout << -1; 
  273.         else cout << left; 
  274.  
  275.         el;
  276.     }
  277.  
  278.     #if ENV 
  279.         time();
  280.     #endif
  281.  
  282.     rt 0;   
  283. }
  284.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vv8ElR
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

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!