Submission #546365

#TimeUsernameProblemLanguageResultExecution timeMemory
546365hoanghq2004Werewolf (IOI18_werewolf)C++14
100 / 100
807 ms175140 KiB
#include <bits/stdc++.h> #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "werewolf.h" using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 4e5 + 10; vector <int> g[N]; int a[N]; struct DSU { int n, ord[N]; int in[N], out[N]; int root[N]; vector <int> e[N]; DSU(int _n) { n = _n; for (int i = 0; i < n; ++i) root[i] = i; } int Find(int u) { return (u == root[u] ? u : root[u] = Find(root[u])); } void Union(int u, int v) { if ((u = Find(u)) == (v = Find(v))) return; e[n].push_back(u); e[n].push_back(v); root[u] = n, root[v] = n; root[n] = n; ++n; } int ti = 0; void dfs(int u) { if (e[u].size()) { in[u] = 1e9, out[u] = - 1e9; for (auto v: e[u]) dfs(v), in[u] = min(in[u], in[v]), out[u] = max(out[u], out[v]); } else { ord[ti] = u; in[u] = out[u] = ti; ++ti; } } void run() { dfs(n - 1); } }; int node[N][2]; vector <pair <int, int> > QL[N], QR[N]; vector <int> st[N * 4]; void build(int id, int L, int R) { if (L == R) { st[id].push_back(a[L]); return; } int mid = L + R >> 1; build(id * 2, L, mid); build(id * 2 + 1, mid + 1, R); st[id].resize(R - L + 1); merge(st[id * 2].begin(), st[id * 2].end(), st[id * 2 + 1].begin(), st[id * 2 + 1].end(), st[id].begin()); } int get(int id, int L, int R, int u, int v, int x, int y) { if (u > R || L > v) return 0; if (u <= L && R <= v) { auto iter = lower_bound(st[id].begin(), st[id].end(), x); if (iter != st[id].end() && *iter <= y) return 1; return 0; } int mid = L + R >> 1; return get(id * 2, L, mid, u, v, x, y) || get(id * 2 + 1, mid + 1, R, u, v, x, y); } vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int m = X.size(); int q = S.size(); for (int i = 0; i < m; ++i) { int u = X[i], v = Y[i]; g[u].push_back(v); g[v].push_back(u); } vector<int> A(q); for (int i = 0; i < q; ++i) { int u = S[i], v = E[i], l = L[i], r = R[i]; QR[l].push_back({u, i}); QL[r].push_back({v, i}); } DSU D1(n), D2(n); for (int u = 0; u < n; ++u) { for (auto v: g[u]) { if (u > v) D1.Union(u, v); } for (auto [x, i]: QL[u]) node[i][0] = D1.Find(x); } for (int u = n - 1; u >= 0; --u) { for (auto v: g[u]) { if (u < v) D2.Union(u, v); } for (auto [x, i]: QR[u]) node[i][1] = D2.Find(x); } D1.run(); D2.run(); for (int i = 0; i < n; ++i) a[i] = D2.in[D1.ord[i]]; build(1, 0, n - 1); for (int i = 0; i < q; ++i) { A[i] = get(1, 0, n - 1, D1.in[node[i][0]], D1.out[node[i][0]], D2.in[node[i][1]], D2.out[node[i][1]]); } return A; } //namespace { // //int read_int() { // int x; // if (scanf("%d", &x) != 1) { // fprintf(stderr, "Error while reading input\n"); // exit(1); // } // return x; //} // //} // namespace // //int main() { // int N = read_int(); // int M = read_int(); // int Q = read_int(); // std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q); // for (int j = 0; j < M; ++j) { // X[j] = read_int(); // Y[j] = read_int(); // } // for (int i = 0; i < Q; ++i) { // S[i] = read_int(); // E[i] = read_int(); // L[i] = read_int(); // R[i] = read_int(); // } // // std::vector<int> A = check_validity(N, X, Y, S, E, L, R); // for (size_t i = 0; i < A.size(); ++i) { // printf("%d\n", A[i]); // } // return 0; //}

Compilation message (stderr)

werewolf.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
werewolf.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = L + R >> 1;
      |               ~~^~~
werewolf.cpp: In function 'int get(int, int, int, int, int, int, int)':
werewolf.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = L + R >> 1;
      |               ~~^~~
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:102:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto [x, i]: QL[u]) node[i][0] = D1.Find(x);
      |                   ^
werewolf.cpp:108:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         for (auto [x, i]: QR[u]) node[i][1] = D2.Find(x);
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...