oj.uz

Submission #1038545

# Submission time Handle Problem Language Result Execution time Memory
1038545 2024-07-29T23:06:30 Z vjudge1 Werewolf (IOI18_werewolf) C++17
34 / 100
 250 ms 93012 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];
    s=pos[s];
    e=pos[e];
    if(s<e) {
      int l=s,r=e,res=0;
      while(l<=r){
        int mid=l+r>>1;
        if(qrymn(s,mid)>=L[i])
          l=mid+1,res=mid;
        else r=mid-1;
      }
      A[i]=qrymx(res,e)<=R[i];
    } else {
      int l=e,r=s,res=0;
      while(l<=r){
        int mid=l+r>>1;
        if(qrymx(e,mid)<=R[i])
          l=mid+1,res=mid;
        else r=mid-1;
      }
      A[i]=qrymn(res,s)>=L[i];
    }
  }
  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]);
      |                                               ~^~
werewolf.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid=l+r>>1;
      |                 ~^~
werewolf.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 93012 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 43 ms 93012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 63072 KB Output is correct
2 Correct 212 ms 71252 KB Output is correct
3 Correct 209 ms 71248 KB Output is correct
4 Correct 229 ms 71248 KB Output is correct
5 Correct 224 ms 71272 KB Output is correct
6 Correct 198 ms 71248 KB Output is correct
7 Correct 250 ms 71260 KB Output is correct
8 Correct 201 ms 71252 KB Output is correct
9 Correct 172 ms 71508 KB Output is correct
10 Correct 192 ms 71404 KB Output is correct
11 Correct 181 ms 71252 KB Output is correct
12 Correct 196 ms 71504 KB Output is correct
13 Correct 195 ms 71260 KB Output is correct
14 Correct 197 ms 71388 KB Output is correct
15 Correct 203 ms 71252 KB Output is correct
16 Correct 218 ms 71252 KB Output is correct
17 Correct 212 ms 71252 KB Output is correct

Subtask #4
0 / 51.0

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