oj.uz

Submission #599076

# Submission time Handle Problem Language Result Execution time Memory
599076 2022-07-19T09:53:41 Z computerbox Werewolf (IOI18_werewolf) C++14
0 / 100
 378 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 355 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 355 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 66032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 355 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -