Submission #600940

#	Time	Username	Problem	Language	Result	Execution time	Memory
600940		Belgutei	Werewolf (IOI18_werewolf)	C++17	34 / 100	410 ms	38768 KiB

werewolf

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

using namespace std;

#define pb push_back
#define ff first
#define ss second

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

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, zereg[30];
void build_tree() {
  zereg[0] = 1;
  for(int i = 0; i < 30; i ++) {
    if(zereg[i] >= n) {level = i; break;}
    zereg[i + 1] = zereg[i] * 2;
  }
  for(int i = 0; i < zereg[level]; i ++) {
    if(i < n) {
      mx[level].pb(a[i]);
    }
    else {
      mx[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]));
    }
  }
}

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

int find(int node) {
  if(parent[node] == node) return node;
  return parent[node] = find(parent[node]);
}

int d_find(int node) {
  if(dad[node] == node) return node;
  return dad[node] = d_find(dad[node]);
}

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;}
  for(int i = 0; i < N; i ++) {parent[i] = i; dad[i] = i;}
  for(int i = 0; i < S.size(); i ++) {
    p[i].ff = L[i];
    p[i].ss = i;
  }
  sort(p, p + S.size());
  build_tree();
  for(int i = 0; i < S.size(); i ++) ans.pb(0);
  //
  for(int j = S.size() - 1; j >= 0; j --) {
    int i = p[j].ss;
    if(S[i] < L[i] || E[i] > R[i]) {continue;}
    if(pos[S[i]] < pos[E[i]]) {
      int A = find(S[i]);
      if(pos[A] >= pos[E[i]]) {ans[i] = 1; continue;}
      while(pos[A] < pos[E[i]]) {
        if(a[pos[A] + 1] >= L[i]) {parent[A] = find(a[pos[A] + 1]); A = parent[A];}
        else break;
      }
      if(pos[A] >= pos[E[i]]) {ans[i] = 1; continue;}
      ret = -1;
      dfs(0,0,pos[A],pos[E[i]]);
      if(ret <= R[i]) {ans[i] = 1; continue;}
    } 
    else {
      int A = d_find(S[i]);
      if(pos[A] <= pos[E[i]]) {ans[i] = 1; continue;}
      while(pos[A] > pos[E[i]]) {
        if(a[pos[A] - 1] >= L[i]) {dad[A] = d_find(dad[a[pos[A] - 1]]); A = dad[A];}
        else break;
      }
      if(pos[A] <= pos[E[i]]) {ans[i] = 1; continue;}
      ret = -1;
      dfs(0,0,pos[E[i]],pos[A]);
      if(ret <= R[i]) {ans[i] = 1; continue;}
    }
  }
  //
  return ans;
}

Compilation message (stderr)

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

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