Submission #1032580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032580		HappyCapybara	Werewolf (IOI18_werewolf)	C++17	34 / 100	1294 ms	37104 KiB

werewolf

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

int n;
vector<int> stx, stn;

void updatex(int pos, int val, int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    stx[node] = val;
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) updatex(pos, val, node*2, tl, tm);
  else updatex(pos, val, node*2+1, tm+1, tr);
  stx[node] = max(stx[node*2], stx[node*2+1]);
}

int queryx(int l, int r, int node=1, int tl=0, int tr=n-1){
  if (l <= tl && tr <= r) return stx[node];
  int tm = (tl+tr)/2;
  int res = -1;
  if (l <= tm) res = max(res, queryx(l, r, node*2, tl, tm));
  if (tm+1 <= r) res = max(res, queryx(l, r, node*2+1, tm+1, tr));
  return res;
}

void updaten(int pos, int val, int node=1, int tl=0, int tr=n-1){
  if (tl == tr){
    stn[node] = val;
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) updaten(pos, val, node*2, tl, tm);
  else updaten(pos, val, node*2+1, tm+1, tr);
  stn[node] = min(stn[node*2], stn[node*2+1]);
}

int queryn(int l, int r, int node=1, int tl=0, int tr=n-1){
  if (l <= tl && tr <= r) return stn[node];
  int tm = (tl+tr)/2;
  int res = 200000;
  if (l <= tm) res = min(res, queryn(l, r, node*2, tl, tm));
  if (tm+1 <= r) res = min(res, queryn(l, r, node*2+1, tm+1, tr));
  return res;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
  n = N;
  vector<vector<int>> g(N);
  for (int i=0; i<X.size(); i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  vector<bool> seen(N, false);
  int cur;
  for (int i=0; i<N; i++){
    if (g[i].size() == 1){
      cur = i;
      break;
    }
  }
  stx = {};
  stx.resize(4*N, -1);
  stn = {};
  stn.resize(4*N, 200000);
  int pos = 0;
  vector<int> v(N);
  while (true){
    seen[cur] = true;
    updatex(pos, cur);
    updaten(pos, cur);
    v[cur] = pos;
    pos++;
    for (int next : g[cur]){
      if (!seen[next]) cur = next;
    }
    if (seen[cur]) break;
  }
  /*for (int x : v) cout << x << " ";
  cout << "\n";*/

  vector<int> A(S.size(), 0);
  for (int i=0; i<S.size(); i++){
    int s = v[S[i]], e = v[E[i]];
    //cout << s << " " << e << "\n";
    if (s < e){
      int l = s, r = e+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryn(l, m) >= L[i]) l = m;
        else r = m;
      }
      int rh = l;
      l = s; r = e+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryx(m-1, r-1) <= R[i]) r = m;
        else l = m;
      }
      int lw = l;
      //cout << lw << " " << rh << "\n";
      if (lw <= rh) A[i] = 1;
    }
    else {
      int l = e, r = s+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryx(l, m) <= R[i]) l = m;
        else r = m;
      }
      int rw = l;
      l = e; r = s+1;
      while (l != r-1){
        int m = (l+r)/2;
        if (queryn(m-1, r-1) >= L[i]) r = m;
        else l = m;
      }
      int lh = l;
      //cout << lh << " " << rw << "\n";
      if (lh <= rw) A[i] = 1;
    }
  }
  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:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i=0; i<X.size(); i++){
      |                 ~^~~~~~~~~
werewolf.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i=0; i<S.size(); i++){
      |                 ~^~~~~~~~~
werewolf.cpp:70:13: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     seen[cur] = true;
      |             ^

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