제출 #102700

#제출 시각아이디문제언어결과실행 시간메모리
102700bert30702늑대인간 (IOI18_werewolf)C++17
100 / 100
2834 ms165872 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; const int MX = 2e5 + 100; vector<int> G[MX], G_mx[MX], G_mn[MX]; int boss_mx[MX], boss_mn[MX]; int l_mx[MX], r_mx[MX], l_mn[MX], r_mn[MX], tmp[MX]; vector<int> ptr_mn[MX], ptr_mx[MX]; vector<int> T[MX * 4]; void build_ptr_mn(int u, int p, int &ptr) { l_mn[u] = ++ptr; tmp[ptr] = u; if(p != -1) { ptr_mn[u].push_back(p); while(ptr_mn[ptr_mn[u].back()].size() >= ptr_mn[u].size()) { ptr_mn[u].push_back(ptr_mn[ptr_mn[u].back()][ptr_mn[u].size() - 1]); } } for(auto it: G_mn[u]) build_ptr_mn(it, u, ptr); r_mn[u] = ptr; } void build_ptr_mx(int u, int p, int &ptr) { l_mx[u] = ++ptr; if(p != -1) { ptr_mx[u].push_back(p); while(ptr_mx[ptr_mx[u].back()].size() >= ptr_mx[u].size()) { ptr_mx[u].push_back(ptr_mx[ptr_mx[u].back()][ptr_mx[u].size() - 1]); } } for(auto it: G_mx[u]) build_ptr_mx(it, u, ptr); r_mx[u] = ptr; } void build_T(int u, int l, int r) { if(l == r) return T[u] = {l_mx[tmp[l]]}, void(); int m = l + r >> 1; build_T(u * 2 + 1, l, m); build_T(u * 2 + 2, m + 1, r); T[u].resize(r - l + 1); merge(T[u * 2 + 1].begin(), T[u * 2 + 1].end(), T[u * 2 + 2].begin(), T[u * 2 + 2].end(), T[u].begin()); } int query_T(int u, int l, int r, int s, int t, int a, int b) { if(l == s and r == t) return lower_bound(T[u].begin(), T[u].end(), a) != upper_bound(T[u].begin(), T[u].end(), b); int m = l + r >> 1; if(t <= m) return query_T(u * 2 + 1, l, m, s, t, a, b); if(s > m) return query_T(u * 2 + 2, m + 1, r, s, t, a, b); return query_T(u * 2 + 1, l, m, s, m, a, b) | query_T(u * 2 + 2, m + 1, r, m + 1, t, a, b); } vector<int> query(int N, vector<int> S, vector<int> T, vector<int> L, vector<int> R) { vector<int> ans; for(int i = 0; i < S.size(); i ++) { for(int j = 2000; j >= 0; j --) { if(ptr_mn[S[i]].empty()) break; j = min(j, (int) ptr_mn[S[i]].size() - 1); if(ptr_mn[S[i]][j] >= L[i]) S[i] = ptr_mn[S[i]][j]; } for(int j = 2000; j >= 0; j --) { if(ptr_mx[T[i]].empty()) break; j = min(j, (int) ptr_mx[T[i]].size() - 1); if(ptr_mx[T[i]][j] <= R[i]) T[i] = ptr_mx[T[i]][j]; } ans.push_back(query_T(0, 1, N, l_mn[S[i]], r_mn[S[i]], l_mx[T[i]], r_mx[T[i]])); } return ans; } int Find_mx(int u) { return boss_mx[u] == u ? u : boss_mx[u] = Find_mx(boss_mx[u]); } int Find_mn(int u) { return boss_mn[u] == u ? u : boss_mn[u] = Find_mn(boss_mn[u]); } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> T, vector<int> L, vector<int> R) { for(int i = 0; i < N; i ++) boss_mx[i] = boss_mn[i] = i; for(int i = 0; i < X.size(); i ++) { G[X[i]].push_back(Y[i]); G[Y[i]].push_back(X[i]); } for(int i = N - 1; i >= 0; i --) { for(auto it: G[i]) { if(it > i and Find_mn(it) != i) { G_mn[i].push_back(Find_mn(it)); boss_mn[Find_mn(it)] = i; } } } for(int i = 0; i < N; i ++) { for(auto it: G[i]) { if(it < i and Find_mx(it) != i) { G_mx[i].push_back(Find_mx(it)); boss_mx[Find_mx(it)] = i; } } } int ptr_mn = 0; build_ptr_mn(0 , -1, ptr_mn); int ptr_mx = 0; build_ptr_mx(N - 1, -1, ptr_mx); build_T(0, 1, N); return query(N, S, T, L, R); }

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

werewolf.cpp: In function 'void build_T(int, int, int)':
werewolf.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'int query_T(int, int, int, int, int, int, int)':
werewolf.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
werewolf.cpp: In function 'std::vector<int> query(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i ++) {
                 ~~^~~~~~~~~~
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:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); 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...