Submission #123200

#	Time	Username	Problem	Language	Result	Execution time	Memory
123200		nvmdava	Werewolf (IOI18_werewolf)	C++17	15 / 100	4022 ms	120056 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];

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;
}
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];
   }
   for(int i = l[1][s]; i <= r[1][s]; i++){
      for(int j = l[0][e]; j <= r[0][e]; j++){
         if(arr[1][i] == arr[0][j]) return 1;
      }
   }
   return 0;
}

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);

   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;
}

Compilation message (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: 0 / 34
• Subtask 4: 0 / 51