Submission #422736

#TimeUsernameProblemLanguageResultExecution timeMemory
422736TangentWerewolf (IOI18_werewolf)C++17
15 / 100
4062 ms32308 KiB
#include "werewolf.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vii; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vii> vvii; typedef vector<vll> vvll; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; #define ffor(i, a, b) for (ll i = a; i < b; i++) #define rep(i, n) ffor(i, 0, n) #define forin(x, a) for (auto &x: a) #define all(a) a.begin(), a.end() std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) { int Q = S.size(); vpii edges, edges2, l, r; rep(i, X.size()) { if (X[i] > Y[i]) { swap(X[i], Y[i]); } edges.emplace_back(X[i], Y[i]); edges2.emplace_back(Y[i], X[i]); } sort(all(edges)); sort(all(edges2)); rep(i, Q) { l.emplace_back(L[i], i); r.emplace_back(R[i], i); } sort(all(l)); sort(all(r)); reverse(all(r)); vii res(Q); vii parent(N, -1), parent2(N, -1); function<int(int)> root, root2; root = [&](int x) { if (parent[x] < 0) { return x; } return parent[x] = root(parent[x]); }; root2 = [&](int x) { if (parent2[x] < 0) { return x; } return parent2[x] = root2(parent2[x]); }; function<void(int, int)> merge, merge2; merge = [&](int x, int y) { int rx = root(x), ry = root(y); if (rx != ry) { if (parent[rx] < parent[ry]) { swap(rx, ry); } parent[ry] += parent[rx]; parent[rx] = ry; } }; merge2 = [&](int x, int y) { int rx = root2(x), ry = root2(y); if (rx != ry) { if (parent2[rx] < parent2[ry]) { swap(rx, ry); } parent2[ry] += parent2[rx]; parent2[rx] = ry; } }; vvii reached(Q); int edge_ind = edges.size() - 1; while (!l.empty()) { int i = l.back().second; l.pop_back(); while (edge_ind >= 0 & edges[edge_ind].first >= L[i]) { merge(edges[edge_ind].first, edges[edge_ind].second); edge_ind--; } ffor(j, L[i], R[i] + 1) { if (root(j) == root(S[i])) { reached[i].emplace_back(j); } } } edge_ind = 0; while (!r.empty()) { int i = r.back().second; r.pop_back(); while (edge_ind < edges2.size() && edges2[edge_ind].first <= R[i]) { merge2(edges2[edge_ind].first, edges2[edge_ind].second); edge_ind++; } forin(j, reached[i]) { if (root2(j) == root2(E[i])) { res[i] = 1; break; } } } return res; }

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
werewolf.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
werewolf.cpp:29:3: note: in expansion of macro 'rep'
   29 |   rep(i, X.size()) {
      |   ^~~
werewolf.cpp:91:21: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   91 |     while (edge_ind >= 0 & edges[edge_ind].first >= L[i]) {
      |            ~~~~~~~~~^~~~
werewolf.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     while (edge_ind < edges2.size() && edges2[edge_ind].first <= R[i]) {
      |            ~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...