제출 #938133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938133		PagodePaiva	늑대인간 (IOI18_werewolf)	C++17	0 / 100	801 ms	38088 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define N 200010
#define inf 1e8

using namespace std;

int v[N];

struct SegtreeMin{
  int tree[4*N];
  int join(int a, int b){
    return min(a, b);
  }
  void build(int node, int l, int r){
    if(l == r){
      tree[node] = v[l];
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  int query(int node, int l, int r, int tl, int tr){
    if(l > tr or tl > r) return inf;
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
  int search(int n, int l, int r, int val, int typ){
      if(query(1, l, r, 1, n) >= val) return 0;
      if(typ == 0){
        while(r-l > 1){
          int mid = (l+r)/2;
          // cout << l << ' ' << r << ' ' << mid << endl;
          int q = query(1, l, mid, 1, n);
          if(q < val) r = mid;
          else l = mid+1;
        }
        if(query(1, l, l, 1, n) < val) return l;
        else return r;
      }
      else {
        while(l < r){
          int mid = (l+r)/2;
          int q = query(1,mid+1, r, 1, n);
          if(q < val) l = mid+1;
          else r = mid;
        }
        return l;
      }
  }
} segmin;


struct SegtreeMax{
  int tree[4*N];
  int join(int a, int b){
    return max(a, b);
  }
  void build(int node, int l, int r){
    if(l == r){
      tree[node] = v[l];
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  int query(int node, int l, int r, int tl, int tr){
    if(l > tr or tl > r) return -1;
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
} segmax;

vector <int> g[N];
int inv[N];

void construct(int n){
  int st = 0, ed = 0;
  for(int i = 1;i <= n;i++){
    if(g[i].size() == 1){ 
      ed = st;
      st = i;
    }
  }
  // cout << st << ' ';
  v[1] = st;
  inv[st] = 1;
  st = g[st][0];
  for(int i = 2;i <= n;i++){ 
    v[i] = st;
    inv[st] = i;
    if(i < n){
      int x = g[st][0];
      if(inv[x] != 0) x = g[st][1];
      st = x;
      }
  }
  return;
}

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) {
  for(int i = 0;i < n-1;i++){
    int a = ++x[i], b = ++y[i];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  construct(n);
  segmin.build(1, 1, n);
  segmax.build(1, 1, n);
  vector <int> res;
  // for(int i = 1;i <= n;i++){
  //   cout << v[i] << ' ' << inv[v[i]] << endl;
  // }
  for(int i = 0;i < s.size();i++){
    int st = ++s[i], ed = ++e[i], lt = ++l[i], rt = ++r[i];
    st = inv[st];
    ed = inv[ed];
    if(v[st] < lt){
      res.push_back(0);
      continue;
    }
    if(v[ed] > rt){
      res.push_back(0);
      continue;
    }
    if(st <= ed){
      int w = segmin.search(n, st, ed, lt, 0);
      if(w == 0){
        res.push_back(1);
        continue;
      }
      int h = segmax.query(1, w, ed, 1, n);
      if(h > rt){
        res.push_back(0);
        continue;
      }
      res.push_back(1);
      continue;
    }
    else{
      int w = segmin.search(n, ed, st, lt, 1);
      if(w == 0){
        res.push_back(1);
        continue;
      }
      int h = segmax.query(1, ed, w, 1, n);
      if(h > rt){
        res.push_back(0);
        continue;
      }
      res.push_back(1);
      continue;
    }
  }
  return res;
  // int Q = S.size();
  // std::vector<int> A(Q);
  // for (int i = 0; i < Q; ++i) {
  //   A[i] = 0;
  // }
  // return A;
}

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

werewolf.cpp: In function 'void construct(int)':
werewolf.cpp:86:15: warning: variable 'ed' set but not used [-Wunused-but-set-variable]
   86 |   int st = 0, ed = 0;
      |               ^~
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:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int i = 0;i < s.size();i++){
      |                 ~~^~~~~~~~~~

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