oj.uz

Submission #1038541

# Submission time Handle Problem Language Result Execution time Memory
1038541 2024-07-29T22:56:58 Z vjudge1 Werewolf (IOI18_werewolf) C++17
0 / 100
 178 ms 93020 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[200100];
int stbmx[200100][20],stbmn[200100][20];
int CC;
int pos[200100];
void dfs(int n,int p) {
  stbmn[pos[n]=++CC][0]=n;
  stbmx[CC][0]=n;
  for(auto i:adj[n])
      if(i-p) dfs(i,n);
}
int qrymx(int l,int r){
  int x=31-__builtin_clz(r-l+1);
  return max(stbmx[l][x],stbmx[r-(1<<x)+1][x]);
}
int qrymn(int l,int r){
  int x=31-__builtin_clz(r-l+1);
  return min(stbmn[l][x],stbmn[r-(1<<x)+1][x]);
}
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) {
  for(int i=0;i<X.size();i++)
    adj[X[i]].push_back(Y[i]),
    adj[Y[i]].push_back(X[i]);
  int lef=0;
  for(int i=0;i<N;i++)
    if(adj[i].size()==1) 
      lef=i;
  memset(stbmx,1,sizeof stbmx);
  memset(stbmn,-1,sizeof stbmn);
  dfs(lef,-1);
  for(int j=1;j<20;j++) for(int i=1;i<N-(1<<j)+2;i++)
    stbmx[i][j]=max(stbmx[i][j-1],stbmx[i+(1<<j-1)][j-1]),
    stbmn[i][j]=min(stbmn[i][j-1],stbmn[i+(1<<j-1)][j-1]);
  int Q=S.size();
  vector<int>A(Q);
  for(int i=0;i<Q;i++){
    int s=S[i],e=E[i],l=L[i],r=R[i];
    s=pos[s];
    e=pos[e];
    if(s<e) {
      for(int i=20;i--;)
        if(stbmn[s][i]>=l)
          s+=1<<i;
      if(s>=e) A[i]=1;
      else A[i]=qrymx(s-1,e)<=r;
    } else {
      for(int i=20;i--;)
        if(stbmx[e][i]<=r)
          e+=1<<i;
      if(e>=s)A[i]=1;
      else A[i]=qrymn(e-1,s)>=l;
    }
  }
  return A;
}

Compilation message

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:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:35:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |     stbmx[i][j]=max(stbmx[i][j-1],stbmx[i+(1<<j-1)][j-1]),
      |                                               ~^~
werewolf.cpp:36:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |     stbmn[i][j]=min(stbmn[i][j-1],stbmn[i+(1<<j-1)][j-1]);
      |                                               ~^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 93020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 93020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 62972 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 42 ms 93020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -