fork download
copy 
  1. /**
  2.  *    author:  mamion
  3.  *    created: Friday 2024-10-18
  4. **/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifdef LOCAL
  10. #include<cpp-dump-main/cpp-dump.hpp>
  11. #define debug(...) cpp_dump(__VA_ARGS__)
  12. CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
  13. CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
  14. CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
  15. #else
  16. #define debug(...)
  17. #endif // LOCAL
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22.  
  23. const int N = 2e4 + 100;
  24. const int zero = N - 2;
  25. const int one = N - 3;
  26.  
  27. int lab[N];
  28. int find(int u) {
  29.     return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  30. }
  31. int join(int u, int v) {
  32.     u = find(u); v = find(v);
  33.     if (u == v) return false;
  34.     if (lab[u] > lab[v]) swap(u, v);
  35.     lab[u] += lab[v];
  36.     lab[v] = u;
  37.     return true;
  38. }
  39.  
  40. int n, m, k;
  41. struct query {
  42.     int u, v; char c;
  43. };
  44. query queries[N];
  45.  
  46. void reset(int mid) {
  47.     lab[zero] = lab[one] = -1;
  48.     for (int i = 1; i <= mid; i++)
  49.         lab[queries[i].u] = lab[queries[i].v] = -1;
  50. };
  51.  
  52. bool check(int mid) {
  53.     reset(mid);
  54.     for (int i = 1; i <= mid; i++) {
  55.         int u = queries[i].u, v = queries[i].v; char c = queries[i].c;
  56.         if (c == '<') {
  57.             join(u, zero);
  58.             join(v, one);
  59.         }
  60.         if (c == '>') {
  61.             join(u, one);
  62.             join(v, zero);
  63.         }
  64.         if (c == '=') join(u, v);
  65.     }
  66.     int z = k - (-lab[find(zero)] - 1);
  67.     if (z == 0) return true;
  68.     bitset<N> dp1[2], dp2[2];
  69.     vector<int> g;
  70.     for (int u = 1; u <= n; u++) {
  71.         if (lab[u] >= 0) continue;
  72.         if (find(u) == find(one)) continue;
  73.         if (find(u) == find(zero)) continue;
  74.         int a = -lab[u];
  75.         g.push_back(a);
  76.     }
  77.     int f = 0, s = 1;
  78.     dp1[f][0] = 1;
  79.     for (int a : g) {
  80.         dp1[s] = dp1[f] | (dp1[f] << a);
  81.         dp2[s] = dp2[f] | (dp2[f] << a) | (dp1[f] & (dp1[f] << a));
  82.         swap(f, s);
  83.     }
  84.     if (dp1[f][z] && dp2[f][z] == 0) return true;
  85.     return false;
  86. }
  87.  
  88. void solve() {
  89.     cin >> n >> m >> k;
  90.     for (int i = 1; i <= m; i++) cin >> queries[i].u >> queries[i].c >> queries[i].v;
  91.  
  92.     if (n == k) {
  93.         cout << 0 << '\n';
  94.         return;
  95.     }
  96.     reset(n);
  97.  
  98.     int ans = -1;
  99.     for (int l = 1, r = m; l <= r;) {
  100.         int mid = (l + r) / 2;
  101.         if (check(mid)) {
  102.             ans = mid;
  103.             r = mid - 1;
  104.         } else l = mid + 1;
  105.     }
  106.     cout << ans << '\n';
  107. }
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  111.  
  112. #ifdef LOCAL
  113.     freopen("main.inp", "r", stdin);
  114.     freopen("main.out", "w", stdout);
  115. #else
  116.     #define file "name"
  117.     if (fopen(file".inp", "r")) {
  118.         freopen(file".inp", "r", stdin);
  119.         freopen(file".out", "w", stdout);
  120.     }
  121. #endif // LOCAL
  122.  
  123.     int T; T = 1; if (1) cin >> T;
  124.     for (int i = 1; i <= T; i++)
  125.     {
  126.         debug(i);
  127.         solve();
  128.     }
  129. }
  130.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
3
6 6 3
1 > 2
3 = 5
4 = 6
1 > 2
2 = 4
1 = 3
4 2 4
1 = 2
3 = 4
4 2 2
1 = 2
3 = 4
stdout
copy 
5
0
-1
https://ideone.com/bIf7dI
language:
C++14 (gcc 8.3)
created:
16 hours 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!