Submission #599076

#	Time	Username	Problem	Language	Result	Execution time	Memory
599076		computerbox	Werewolf (IOI18_werewolf)	C++14	0 / 100	378 ms	524288 KiB

werewolf

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

vector<int>adj[2 * 100010];
vector<int>massiv;

void dfs(int v, int p)
{
  massiv.push_back(v);
  for(auto to: adj[v])
  {
    if(to == p)continue;
    dfs(to, v);
  }
}

int dpmin[2 * 100010][21];
int dpmax[2 * 100010][21];

int query(int l, int r, int sig)
{
  if(sig == 0)
  {
    int k = log(r - l + 1) / log(2);
    return ((massiv[dpmin[l][k]] < massiv[dpmin[r - (1 << k) + 1][k]]) ? dpmin[l][k] : dpmin[r - (1 << k) + 1][k]);
  }
  else
  {
    int k = log(r - l + 1) / log(2);

    return ((massiv[dpmax[l][k]] > massiv[dpmax[r - (1 << k) + 1][k]]) ? dpmax[l][k] : dpmax[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) {
  vector<int>A;
  for(int i = 0; i < N - 1; i++)
  {
    int x = X[i];
    int y = Y[i];
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  int Q = (int)S.size();
  dfs(N - 1, N - 1);
  for(int i = 0; i < N; i++){dpmin[i][0] = i; dpmax[i][0] = i;}
  for(int raz = 1; (1 << raz) <= N; raz++)
  {

    for(int i = 0; i + (1 << (raz - 1)) < N; i++)
    {
      if(massiv[dpmin[i][raz - 1]] <  massiv[dpmin[i + (1 << (raz - 1))][raz - 1]])dpmin[i][raz] = dpmin[i][raz - 1];
      else dpmin[i][raz] = dpmin[i + (1 << (raz - 1))][raz - 1];

      if(massiv[dpmax[i][raz - 1]] >  massiv[dpmax[i + (1 << (raz - 1))][raz - 1]])dpmax[i][raz] = dpmax[i][raz - 1];
      else dpmax[i][raz] = dpmax[i + (1 << (raz - 1))][raz - 1];
    }
  }

  vector<int>ps(N + 1, 0);

  for(int i = 0; i < N; i++)
  {
    ps[massiv[i]] = i;
  }

  for (int i = 0; i < Q; ++i) {
    int l = S[i];
    int r = E[i];
    int a = L[i];
    int b = R[i];

    int lg = ps[l];
    int rg = ps[r];

    if(lg > rg)swap(lg, rg);

    int posa = ps[a];
    int posb = ps[b];

    if(posa > posb)swap(posa, posb);

    int posm = query(posa, posb, 0);
    int posmm = query(posa, posb, 1);



    int posm1 = query(lg, max(lg, posa - 1), 0);
    int posmm1 = query(lg, max(lg, posa - 1), 1);



    int posm2 = query(min(posb + 1, rg), rg, 0);
    int posmm2 = query(min(posb + 1, rg), rg, 1);


    if(massiv[posmm] < a  || massiv[posm] > b)A.push_back(0);
    else if((massiv[posm1] < r  || massiv[posmm1] < r) && posa - 1 >= lg)A.push_back(0);
    else if((massiv[posm2] > l || massiv[posmm2] > l) && posb + 1 <= rg)A.push_back(0);
    else A.push_back(1);

  }
  return A;
}

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