Submission #580588

#	Time	Username	Problem	Language	Result	Execution time	Memory
580588		Vanilla	Werewolf (IOI18_werewolf)	C++17	15 / 100	4050 ms	51180 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn_12 = 3e3 + 2;
const int maxn_3 = 2e5 + 2;
const int lg = 19;
vector <int> ad [maxn_3];
bitset <maxn_12> vis1, vis2;
int act[maxn_3];
int sp[2][maxn_3][lg]; // sp[0] -> min r, sp[1] -> max l

int lg2(int x) {
    int ct = 0;
    int k = 1;
    while (k <= x) {
        k *= 2; ct++;
    }
    return ct-1;
}

void dfs1 (int u, int l, int r) {
  vis1[u] = 1;
  for (int v: ad[u]) {
    if (v < l || vis1[v]) continue;
    dfs1(v, l, r);
  }
}

int dfs2 (int u, int l, int r) {
  vis2[u] = 1;
  bool b = (vis1[u]);
  for (int v: ad[u]) {
    if (v > r || vis2[v]) continue;
    b|=dfs2(v, l, r);
  }
  return b;  
}

void label (int u, int p, int nr) {
  act[u] = nr;
  for (int v: ad[u]) {
    if (v == p) continue;
    label(v, u, nr + 1);
  }
}

int query0 (int l, int r) {
  int k = lg2(r - l + 1);
  return min(sp[0][l][k], sp[0][r - (1 << k) + 1][k]);
}

int query1 (int l, int r) {
  int k = lg2(r - l + 1);
  return max(sp[1][l][k], sp[1][r - (1 << k) + 1][k]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  for (int i = 0; i < X.size(); i++){
    ad[X[i]].push_back(Y[i]);
    ad[Y[i]].push_back(X[i]);
  }
  int Q = S.size();
  vector<int> A(Q);
//   if (0){
  if (N <= 3000 && Q <= 3000 && X.size() <= 6000){
    for (int i = 0; i < Q; ++i) {
      vis1 = vis2 = 0;
      dfs1(S[i], L[i], R[i]);
      A[i] = dfs2(E[i], L[i], R[i]);
    }
  }
  else {
    for (int i = 0; i < N; i++){
      if (ad[i].size() == 1) {
        label(i, -1, 0);
		break;
      }
      for (int i = 0; i < N; i++){
        sp[0][i][0] = R[act[i]];
        sp[1][i][0] = L[act[i]];
      }
      for (int k = 1; k < lg; k++){
        for (int i = 0; i + (1 << k) - 1 < N; i++){
          sp[0][i][k] = min(sp[0][i][k-1], sp[0][i + (1 << (k - 1))][k-1]);
          sp[1][i][k] = max(sp[1][i][k-1], sp[1][i + (1 << (k - 1))][k-1]);
        }
      }
    }
	for (int i = 0; i < Q; ++i) {
		int n1 = act[S[i]], n2 = act[R[i]];
		if (n1 < n2){ 
			int l = n1, r = n2, f1 = -1, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query0(n1, mid) >= S[i]) {
					f1 = mid;
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			l = n1, r = n2, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query1(mid, n2) <= R[i]) {
					f2 = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			A[i] = (f1 >= f2);
		}
		else {
			// swap(n1, n2);
			int l = n1, r = n2, f1 = -1, f2 = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query1(n1, mid) <= R[i]) {
					f1 = mid;
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			while (l <= r) {
				int mid = (l + r) / 2;
				if (query0(mid, n2) >= S[i]) {
					f2 = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			l = n1, r = n2, f2 = -1;
			A[i] = (f1 >= f2);
		}
		
    }
  }
  return A;
}

Compilation message (stderr)

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:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 0; i < X.size(); i++){
      |                   ~~^~~~~~~~~~

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