제출 #969162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969162		duckindog	늑대인간 (IOI18_werewolf)	C++17	34 / 100	1749 ms	45824 KiB

werewolf

#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 f[N << 2][2];
void build(int s, int l, int r) { 
  if (l == r) { 
    f[s][0] = f[s][1] = a[l];
    return;
  }
  int mid = l + r >> 1;
  build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  f[s][0] = min(f[s << 1][0], f[s << 1 | 1][0]);
  f[s][1] = max(f[s << 1][1], f[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 f[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 f[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 (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:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:75:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:95:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:105:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |             int mid = lt + rt >> 1;
      |                       ~~~^~~~
werewolf.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^
werewolf.cpp:54:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     dfs(root);
      |     ~~~^~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51