제출 #123207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123207		nvmdava	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1387 ms	184172 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

int p[2][200005][20];
int tp[2][200005];
int d[2][200005][20];
vector<int> adj[200005];
vector<int> child[2][200005];
int n ;
int find(int i, int id){
   if(i == tp[id][i]){
      return i;
   }
   return tp[id][i] = find(tp[id][i], id);
}
void build(int i, int id){
   for(int x : adj[i]){
      if((id == 0) ^ (x > i) == 1){
         x = find(x, id);
         if(x == i) continue;
         p[id][x][0] = i;
         tp[id][x] = i;
      }
   }
}
int cnt = 0;
int l[2][200005], r[2][200005];
int arr[2][200005];
int inv[200005];
void dfs(int v, int id){
   if((id == 1 && v == 0) || (id == 0 && v == n - 1)){

   } else {
      d[id][v][0] = id == 0 ? max(v, p[id][v][0]) : min(v, p[id][v][0]);
      for(int j = 1; j < 20; j++){
         if(p[id][v][j - 1] == -1) break;
         p[id][v][j] = p[id][p[id][v][j - 1]][j - 1];
         d[id][v][j] = id == 0 ? max(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]) : min(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]);
      }
   }
   l[id][v] = ++cnt;
   arr[id][cnt] = v;
   for(int x :child[id][v]){
      dfs(x, id);
   }
   r[id][v] = cnt;
}

vector<int> seg[530000];
void builder(int id, int l, int r){
   if(l == r){
      seg[id].push_back(arr[0][l]);
      return;
   }
   int m = (l + r) >> 1, id1 = id << 1, id2 = id << 1 | 1, it1 = 0, it2;
   builder(id1, l, m);
   builder(id2, m + 1, r);
   int sz1 = seg[id1].size();
   int sz2 = seg[id2].size();
   while(it1 != sz1 && it2 != sz2){
      if(seg[id1][it1] > seg[id2][it2])
         seg[id].push_back(seg[id2][it2++]);
      else
         seg[id].push_back(seg[id1][it1++]);
   }
   while(it1 != sz1)
         seg[id].push_back(seg[id1][it1++]);
   while(it2 != sz2)
         seg[id].push_back(seg[id2][it2++]);
}

bool query(int id, int l, int r, int L, int R, int D, int U){
   if(r < L || l > R) return 0;
   if(l >= L && r <= R){
      return 0 != upper_bound(seg[id].begin(), seg[id].end(), U) - lower_bound(seg[id].begin(), seg[id].end(), D);
   }
   int m = (l + r) >> 1;
   if(query(id << 1, l, m, L, R, D, U)) return 1;
   if(query(id << 1 | 1, m + 1, r, L, R, D, U)) return 1;
   return 0;
}


bool answer(int s, int e, int L, int R){
   for(int i = 19; i >= 0; i--){
      if(p[1][s][i] != -1 && d[1][s][i] >= L)
         s = p[1][s][i];
      if(p[0][e][i] != -1 && d[0][e][i] <= R)
         e = p[0][e][i];
   }
   return query(1, 1, n, l[0][e], r[0][e], l[1][s], r[1][s]);
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                              vector<int> L, vector<int> R) {
   memset(p, -1, sizeof p);
   for(int i = 0; i < N; i++){
      tp[0][i] = tp[1][i] = i;
   }
   n = N;
   for(int i = X.size() - 1; i >= 0; i--){
      adj[X[i]].push_back(Y[i]);
      adj[Y[i]].push_back(X[i]);
   }
   for(int i = 0; i < N; i++)
      build(i, 0);
   for(int i = N - 1; i >= 0; i--)
      build(i, 1);

   for(int i = 1; i < N; i++)
      child[1][p[1][i][0]].push_back(i);
   for(int i = N - 2; i >= 0; i--)
      child[0][p[0][i][0]].push_back(i);
   cnt = 0; dfs(0, 1);
   cnt = 0; dfs(N - 1, 0);
   for(int i = 1; i <= n; i++){
      inv[arr[1][i]] = i;
   }
   for(int i = 1; i <= n; i++){
      arr[0][i] = inv[arr[0][i]];
   }
   builder(1, 1, n);
   int Q = S.size();
   vector<int> A(Q);
   for (int i = 0; i < Q; ++i) {
      A[i] = answer(S[i], E[i], L[i], R[i]);
   }
   return A;
}

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

werewolf.cpp: In function 'void build(int, int)':
werewolf.cpp:19:30: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
       if((id == 0) ^ (x > i) == 1){
                      ~~~~~~~~^~~~

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