Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // I hate Bitset, I hate my Brain, I hate my Life :(
- #define task ""
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <bitset>
- #include <vector>
- #include <algorithm>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 4e5 + 5;
- struct dsu
- {
- int par[N];
- dsu()
- {
- memset(par, -1, sizeof par);
- }
- int findpar(int v)
- {
- return par[v] < 0 ? v : par[v] = findpar(par[v]);
- }
- void Merge(int u, int v)
- {
- u = findpar(u);
- v = findpar(v);
- if (u == v)
- return;
- if (par[u] < par[v])
- swap(u, v);
- par[v] += par[u];
- par[u] = v;
- }
- } f;
- int n, m, k, val[2];
- int u[N], v[N];
- char c[N];
- void Read()
- {
- cin >> n >> m >> k;
- for (int i = 1; i <= m; ++i)
- cin >> u[i] >> c[i] >> v[i];
- }
- bool Check(int m)
- {
- for (int i = 1; i <= n + 2; ++i)
- f.par[i] = -1;
- for (int i = 1; i <= m; ++i)
- {
- if (c[i] == '<' || c[i] == '>')
- {
- if (c[i] == '>')
- swap(u[i], v[i]);
- f.Merge(u[i], val[0]);
- f.Merge(v[i], val[1]);
- if (c[i] == '>')
- swap(u[i], v[i]);
- }
- else
- f.Merge(u[i], v[i]);
- }
- vector<pair<int, int>> s;
- for (int i = 1; i <= n; ++i)
- if (f.findpar(i) != f.findpar(val[0]) && f.findpar(i) != f.findpar(val[1]))
- s.emplace_back(f.findpar(i), -f.par[f.findpar(i)]);
- sort(s.begin(), s.end());
- s.resize(unique(s.begin(), s.end()) - s.begin());
- bitset<20005> dp1, dp2;
- int tmp = k - (-f.par[f.findpar(val[0])]) + 1;
- dp1[0] = 1;
- for (auto i : s)
- {
- dp2 |= dp2 << i.second;
- dp2 |= dp1 & (dp1 << i.second);
- dp1 |= dp1 << i.second;
- }
- return dp1[tmp] && !(dp2[tmp]);
- }
- void Solve()
- {
- if (k == 0 || k == n)
- {
- cout << "0\n";
- return;
- }
- val[0] = n + 1;
- val[1] = n + 2;
- int l = 1, mid, h = m;
- while (l <= h)
- {
- mid = (l + h) / 2;
- if (Check(mid))
- h = mid - 1;
- else
- l = mid + 1;
- }
- if (l > m)
- cout << "-1\n";
- else
- cout << l << "\n";
- }
- void Destroy()
- {
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- int t;
- for (cin >> t; t--;)
- {
- Read();
- Solve();
- Destroy();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement