Submission #600649

#	Time	Username	Problem	Language	Result	Execution time	Memory
600649		Belgutei	Werewolf (IOI18_werewolf)	C++17	0 / 100	4064 ms	37196 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

vector<int> edge[200005];
bool visited[200005], ok;
int n, pos[200005];
int l,r;
vector<int > mn[30],mx[30],a,ans;

void dfs(int node) {
  visited[node] = 1;
  pos[node] = a.size();
  a.pb(node);
  for(auto x: edge[node]) if(visited[x] == 0) dfs(x);
}

int level, ret;
void build_tree() {
  for(int i = 0; i < 30; i ++) {
    if((1 << i) >= n) {level = i; break;}
  }
  for(int i = 0; i < (1 << level); i ++) {
    if(i < n) {
      mx[level].pb(a[i]);
      mn[level].pb(a[i]);
    }
    else {
      mx[level].pb(0);
      mn[level].pb(0);
    }
  }
  for(int i = level - 1; i >= 0; i --) {
    for(int j = 1; j < mx[i + 1].size(); j += 2) {
      mx[i].pb(max(mx[i + 1][j], mx[i + 1][j - 1]));
      mn[i].pb(min(mn[i + 1][j], mn[i + 1][j - 1]));
    }
  }
}

void dfs(int k, int x, int type, int L, int R) {
  int y = (1 << (level - k)) * x;
  int z = (1 << (level - k)) * (x + 1) - 1;
  if(L <= y && z <= R) {
    if(type == 0) ret = min(ret, mn[k][x]);
    else ret = max(ret, mx[k][x]);
    return;
  }
  if(z < L || y > R || k == level) return;
  dfs(k + 1, x * 2, type, L, R);
  dfs(k + 1, x * 2 + 1, type, L, R);
}

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) {
  n = N;
  for(int i = 0; i < X.size(); i ++) {
    edge[X[i]].pb(Y[i]);
    edge[Y[i]].pb(X[i]);
  }
  for(int i =  0; i < N; i ++) if(edge[i].size() == 1) {dfs(i); break;}
  build_tree();
  for(int i = 0; i < S.size(); i ++) {
    if(S[i] < L[i] || E[i] > R[i]) {ans.pb(0); continue;}
    if(pos[S[i]] <= pos[E[i]]) {
      l = pos[S[i]];
      r = pos[R[i]];
      while(l < r) {
        int mid = (l + r + 1) / 2;
        ret = 1e9;
        dfs(0,0,0,pos[S[i]],mid);
        if(ret >= L[i]) l = mid;
        else r = mid - 1;
      }
      if(a[l] == R[i]) {ans.pb(1); continue;}
      ret = 0;
      dfs(0,0,1,l + 1, pos[R[i]]);
      if(ret <= R[i]) ans.pb(1);
      else ans.pb(0);
    }
    else {
      l = pos[S[i]];
      r = pos[R[i]];
      while(l < r) {
        int mid = (l + r + 1) / 2;
        ret = 1e9;
        dfs(0,0,0,mid, pos[E[i]]);
        if(ret >= L[i]) r = mid;
        else r = mid + 1;
      }
      if(a[l] == R[i]) {ans.pb(1); continue;}
      ret = 0;
      dfs(0,0,1,l + 1, pos[R[i]]);
      if(ret <= R[i]) ans.pb(1);
      else ans.pb(0);
    }
  }
  return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void build_tree()':
werewolf.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j = 1; j < mx[i + 1].size(); j += 2) {
      |                    ~~^~~~~~~~~~~~~~~~~~
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:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int i = 0; i < X.size(); i ++) {
      |                  ~~^~~~~~~~~~
werewolf.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i = 0; i < S.size(); i ++) {
      |                  ~~^~~~~~~~~~

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