제출 #969164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969164		duckindog	늑대인간 (IOI18_werewolf)	C++17	49 / 100	1796 ms	37680 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 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);
      |     ~~~^~~~~~

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