제출 #547783

#제출 시각아이디문제언어결과실행 시간메모리
547783vovamr늑대인간 (IOI18_werewolf)C++14
15 / 100
932 ms524288 KiB
#include "werewolf.h" #include <bits/stdc++.h> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } const int N = 6e6 + 200; ve<int> gr1[N]; int p1[N], w1 = 0; inline int par1(int v) { if (p1[v] == v) { return v; } return (p1[v] = par1(p1[v])); } inline void add1(int a, int b) { a = par1(a), b = par1(b); if (a == b) return; int c = w1++; p1[a] = p1[b] = p1[c] = c; gr1[c].pb(a); if (a ^ b) gr1[c].pb(b); } int ti1 = 0; int in1[N], out1[N]; inline void dfs1(int v) { in1[v] = ti1++; for (auto &to : gr1[v]) dfs1(to); out1[v] = ti1 - 1; } ve<int> gr2[N]; int p2[N], w2 = 0; inline int par2(int v) { if (p2[v] == v) { return v; } return (p2[v] = par2(p2[v])); } inline void add2(int a, int b) { a = par2(a), b = par2(b); if (a == b) return; int c = w2++; p2[a] = p2[b] = p2[c] = c; gr2[c].pb(a); if (a ^ b) gr2[c].pb(b); } int ti2 = 0; int in2[N], out2[N]; inline void dfs2(int v) { in2[v] = ti2++; for (auto &to : gr2[v]) dfs2(to); out2[v] = ti2 - 1; } struct node { node *l = nullptr; node *r = nullptr; int s = 0; node() {} node(int x) : s(x) {} }; inline void upd(node *v, int vl, int vr, int pos, int x) { if (vl == vr) return void(v->s += x); int m = vl + vr >> 1; if (pos <= m) { if (!v->l) v->l = new node(); upd(v->l, vl, m, pos, x); } else { if (!v->r) v->r = new node(); upd(v->r, m + 1, vr, pos, x); } v->s = 0; if (v->l) v->s += v->l->s; if (v->r) v->s += v->r->s; } inline int get(node *v, int vl, int vr, int l, int r) { if (!v || l > r) return 0; else if (vl == l && vr == r) return v->s; int m = vl + vr >> 1; int a = get(v->l, vl, m, l, min(r, m)); int b = get(v->r, m + 1, vr, max(l, m + 1), r); return a + b; } node *t[4 * N]; int L = 0, R = N; inline void upd(int v, int vl, int vr, int x, int y, int d) { if (!t[v]) t[v] = new node(); upd(t[v], L, R, y, d); if (vl == vr) return; int m = vl + vr >> 1; if (x <= m) upd(2 * v + 1, vl, m, x, y, d); else upd(2 * v + 2, m + 1, vr, x, y, d); } inline int get(int v, int vl, int vr, int l, int r, int l1, int r1) { if (l > r) return 0; else if (vl == l && vr == r) return (!t[v] ? 0 : get(t[v], L, R, l1, r1)); int m = vl + vr >> 1; int a = get(2 * v + 1, vl, m, l, min(r, m), l1, r1); int b = get(2 * v + 2, m + 1, vr, max(l, m + 1), r, l1, r1); return a + b; } 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 n = N; int m = sz(X); int q = sz(S); ve<array<int,3>> e(m); for (int i = 0; i < m; ++i) { int v, u; tie(v, u) = mpp(X[i], Y[i]); e[i] = {min(v, u), v, u}; } sort(all(e)); w1 = w2 = n; for (int i = 0; i < n; ++i) p1[i] = p2[i] = i; ve<array<int,5>> que(q); for (int i = 0; i < q; ++i) que[i] = {S[i], E[i], L[i], R[i], i}; sort(all(que), [](const auto &a, const auto &b) { return a[2] > b[2]; }); ve<int> rt1(q), rt2(q); int ptr = sz(e) - 1, ptr1 = 0; for (auto &[v, u, l, r, id] : que) { while (~ptr && e[ptr][0] >= l) { add1(e[ptr][1], e[ptr][2]); --ptr; } rt1[id] = par1(v); } for (int i = 0; i < m; ++i) { int v, u; tie(v, u) = mpp(X[i], Y[i]); e[i] = {max(v, u), v, u}; } sort(all(e)); sort(all(que), [](const auto &a, const auto &b) { return a[3] < b[3]; }); for (auto &[v, u, l, r, id] : que) { while (ptr1 < sz(e) && e[ptr1][0] <= r) { add2(e[ptr1][1], e[ptr1][2]); ++ptr1; } rt2[id] = par2(u); } for (int i = 0; i < w1; ++i) if (p1[i] == i) dfs1(i); for (int i = 0; i < w2; ++i) if (p2[i] == i) dfs2(i); /* cout << '\n'; for (int i = 0; i < n; ++i) cout << in1[i] << " " << in2[i] << '\n'; cout << '\n'; for (int i = 0; i < q; ++i) { cout << "query " << i + 1 << ": " << '\n'; cout << "vertices >= l: [" << in1[rt1[i]] << ", " << out1[rt1[i]] << "]" << '\n'; cout << "vertices <= r: [" << in2[rt2[i]] << ", " << out2[rt2[i]] << "]" << '\n'; cout << '\n'; } cout << '\n'; */ int me = ti1; ve<int> ans(q); for (int i = 0; i < n; ++i) upd(0, 0, me, in1[i], in2[i], 1); for (int i = 0; i < q; ++i) ans[i] = get(0, 0, me, in1[rt1[i]], out1[rt1[i]], in2[rt2[i]], out2[rt2[i]]) > 0; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'void upd(node*, int, int, int, int)':
werewolf.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'int get(node*, int, int, int, int)':
werewolf.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'void upd(int, int, int, int, int, int)':
werewolf.cpp:91:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |  int m = vl + vr >> 1;
      |          ~~~^~~~
werewolf.cpp: In function 'int get(int, int, int, int, int, int, int)':
werewolf.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |  int m = vl + vr >> 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:127:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |  for (auto &[v, u, l, r, id] : que) {
      |             ^
werewolf.cpp:141:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |  for (auto &[v, u, l, r, id] : que) {
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...