제출 #969164

#제출 시각아이디문제언어결과실행 시간메모리
969164duckindog늑대인간 (IOI18_werewolf)C++17
49 / 100
1796 ms37680 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; const int N = 200'000 + 10; vector<int> ad[N]; int a[N], rvs[N], it; void dfs(int u, int p = -1) { a[it] = u; rvs[u] = it++; for (const auto& v : ad[u]) if (v != p) dfs(v, u); } int g[N << 2][2]; void build(int s, int l, int r) { if (l == r) { g[s][0] = g[s][1] = a[l]; return; } int mid = l + r >> 1; build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r); g[s][0] = min(g[s << 1][0], g[s << 1 | 1][0]); g[s][1] = max(g[s << 1][1], g[s << 1 | 1][1]); } int getmi(int s, int l, int r, int u, int v) { if (v < l || u > r) return 200'000; if (u <= l && r <= v) return g[s][0]; int mid = l + r >> 1; return min(getmi(s << 1, l, mid, u, v), getmi(s << 1 | 1, mid + 1, r, u, v)); } int getma(int s, int l, int r, int u, int v) { if (v < l || u > r) return -1; if (u <= l && r <= v) return g[s][1]; int mid = l + r >> 1; return max(getma(s << 1, l, mid, u, v), getma(s << 1 | 1, mid + 1, r, u, v)); } 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(), q = s.size(); bool line = true; for (int i = 0; i < m; ++i) { int u = x[i], v = y[i]; ad[u].push_back(v); ad[v].push_back(u); line &= (ad[u].size() <= 2 && ad[v].size() <= 2); } if (n <= 3000 && m <= 6000 && q <= 3000) { vector<int> answer; for (int i = 0; i < q; ++i) { vector<vector<int>> f(n, vector<int>(2)); vector<int> mk(n); for (int j = 0; j < n; ++j) mk[j] = (j < l[i] ? 0 : j <= r[i] ? 1 : 2); queue<int> que; f[s[i]][0] = f[s[i]][mk[s[i]] == 1] = true; que.push(s[i]); while (que.size()) { auto u = que.front(); que.pop(); for (const auto& v : ad[u]) { if (f[v][0] && f[v][1]) continue; pair<int, int> pre = {f[v][0], f[v][1]}; if (mk[v] >= 1) f[v][0] |= f[u][0]; if (mk[v] <= 1) f[v][1] |= (f[u][1] || mk[v] == 1); if (make_pair(f[v][0], f[v][1]) != pre) que.push(v); } } answer.push_back(f[e[i]][1]); } return answer; } if (line) { int root; for (int i = 0; i < n; ++i) if (ad[i].size() == 1) root = i; dfs(root); build(1, 0, n - 1); vector<int> answer; for (int i = 0; i < q; ++i) { if (rvs[s[i]] < rvs[e[i]]) { int st = rvs[s[i]], ed = rvs[e[i]]; int vegan = -1; { int lt = st, rt = ed; while (lt <= rt) { int mid = lt + rt >> 1; if (getma(1, 0, n - 1, mid, ed) > r[i]) lt = (vegan = mid) + 1; else rt = mid - 1; } } int meat = -1; { int lt = st, rt = ed; while (lt <= rt) { int mid = lt + rt >> 1; if (getmi(1, 0, n - 1, st, mid) < l[i]) rt = (meat = mid) - 1; else lt = mid + 1; } } if (meat == -1 || vegan == -1) { answer.push_back(1); continue; } if (meat <= vegan + 1) answer.push_back(0); else answer.push_back(1); } else { int st = rvs[e[i]], ed = rvs[s[i]]; int vegan = -1; { int lt = st, rt = ed; while (lt <= rt) { int mid = lt + rt >> 1; if (getma(1, 0, n - 1, st, mid) > r[i]) rt = (vegan = mid) - 1; else lt = mid + 1; } } int meat = -1; { int lt = st, rt = ed; while (lt <= rt) { int mid = lt + rt >> 1; if (getmi(1, 0, n - 1, mid, ed) < l[i]) lt = (meat = mid) + 1; else rt = mid - 1;; } } if (meat == -1 || vegan == -1) { answer.push_back(1); continue; } if (meat >= vegan - 1) answer.push_back(0); else answer.push_back(1); } } return answer; } }

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

werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = l + r >> 1;
      |             ~~^~~
werewolf.cpp: In function 'int getmi(int, int, int, int, int)':
werewolf.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
werewolf.cpp: In function 'int getma(int, int, int, int, int)':
werewolf.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   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:92:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:102:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:122:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:132:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
  150 | }
      | ^
werewolf.cpp:81:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dfs(root);
      |     ~~~^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...