Submission #806815

#	Time	Username	Problem	Language	Result	Execution time	Memory
806815		Benmath	Werewolf (IOI18_werewolf)	C++14	15 / 100	1887 ms	25944 KiB

werewolf

#include <cstdio>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>
#include "werewolf.h"

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace
using namespace std;
int treemax[800001];
int treemin[800001];
void updatemax(int node,int start,int end,int idx,int val){
if(start==end){
treemax[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
updatemax(2*node,start,mid,idx,val);
}else{
updatemax(2*node,mid+1,end,idx,val);
}

treemax[node]=max(treemax[2*node],treemax[2*node+1]);
}
}
void updatemin(int node,int start,int end,int idx,int val){
if(start==end){
treemin[node]=val;
}else{
int mid=(start+end)/2;
if(start<=idx and idx<=mid){
updatemin(2*node,start,mid,idx,val);
}else{
updatemin(2*node,mid+1,end,idx,val);
}

treemin[node]=min(treemin[2*node],treemin[2*node+1]);
}
}
int querymax(int node,int start,int end,int l,int r){
if(l>end or r<start){
return 0;
}
if(l<=start and end<=r){
return treemax[node];
}
int mid=(start+end)/2;
return max(querymax(2*node,start,mid,l,r),querymax(2*node+1,mid+1,end,l,r));
}
int querymin(int node,int start,int end,int l,int r){
if(l>end or r<start){
return 1e9;
}
if(l<=start and end<=r){
return treemin[node];
}
int mid=(start+end)/2;
return min(querymin(2*node,start,mid,l,r),querymin(2*node+1,mid+1,end,l,r));
}
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) {
  int q = S.size();
  std::vector<int> A(q);
  vector<int>adjl[n+1];
  int m=X.size();  for(int i=0;i<m;i++){
  adjl[X[i]].push_back(Y[i]);
  adjl[Y[i]].push_back(X[i]);
  }
  if(n<=3000 and m<=6000 and q<=3000){

  for (int i = 0; i < q; ++i) {
    A[i] = 0;
    int x=S[i];
    int y=E[i];
    int l=L[i];
    int r=R[i];
    
    int wolf[n+1];
    int human[n+1];
    for(int j=0;j<n;j++){
  wolf[j]=0;
  human[j]=0;
    
    
  }
  queue<int>q;
  q.push(x);
  human[x]++;
  while(!q.empty()){
  int a=q.front();
  q.pop();
  for(int j=0;j<adjl[a].size();j++){
  if(human[adjl[a][j]]==0 and adjl[a][j]>=l){
  human[adjl[a][j]]++;
  q.push(adjl[a][j]);
  }
  }
  }
  q.push(y);
  wolf[y]++;
   while(!q.empty()){
  int a=q.front();
  q.pop();
  for(int j=0;j<adjl[a].size();j++){
  if(wolf[adjl[a][j]]==0 and adjl[a][j]<=r){
  wolf[adjl[a][j]]++;
  q.push(adjl[a][j]);
  }
  }
  }
  for(int j=0;j<n;j++){
  if(human[j]>0 and wolf[j]>0){
  A[i]++;
  }
  }
  A[i]=min(A[i],1);
  }
  return A;
  }else{
  int loc[n];  int vis[n+1];
  int value[n];
  for(int i=0;i<n;i++){
  vis[i]=0;
  }
  for(int i=0;i<n;i++){
  if(adjl[i].size()==1){

  int ro=0;
  int t1=0;
  int so=i;

  while(t1==0){
  loc[so]=ro;
  value[ro]=so;
  vis[so]++;
  ro++;
  int bro=0;
  int so1=so;
  for(int j=0;j<adjl[so1].size();j++){
  if(vis[adjl[so1][j]]==0){
  so=adjl[so1][j];
  
  bro++;
  break;
  }
  }
  if(bro==0){
  break;
  }
  }
  break;
  }
  }
 for(int i=0;i<n;i++){
 updatemin(1,0,n-1,i,value[i]);
 updatemax(1,0,n-1,i,value[i]);
 }
 for(int i=0;i<q;i++){
 A[i] = 0;
    int x=S[i];
    int y=E[i];
    int x1=loc[S[i]];
    int y1=loc[E[i]];
    int l1=L[i];
    int r1=R[i];
    int ans1=x;
    int ans2=y;
    int l=x1;
    int r=n-1;
    while(l<=r){
    int mid=(l+r)/2;
    int t=querymin(1,0,n-1,x1,mid);
    if(t>=l){
    ans1=max(ans1,mid);
    l=mid+1;
    }else{
    r=mid-1;
    }
    }
    l=0;
    r=y1;
    while(l<=r){
    int mid=(l+r)/2;
    int t=querymax(1,0,n-1,mid,y1);
    if(t<=r){
    ans2=min(ans2,mid);
    r=mid-1;
    }else{
    l=mid+1;
    }
    }
    if(ans1>=ans2){
    A[i]++;
    }
 }
 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:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int j=0;j<adjl[a].size();j++){
      |               ~^~~~~~~~~~~~~~~
werewolf.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int j=0;j<adjl[a].size();j++){
      |               ~^~~~~~~~~~~~~~~
werewolf.cpp:150:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for(int j=0;j<adjl[so1].size();j++){
      |               ~^~~~~~~~~~~~~~~~~
werewolf.cpp:175:9: warning: unused variable 'l1' [-Wunused-variable]
  175 |     int l1=L[i];
      |         ^~
werewolf.cpp:176:9: warning: unused variable 'r1' [-Wunused-variable]
  176 |     int r1=R[i];
      |         ^~
werewolf.cpp: At global scope:
werewolf.cpp:9:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
    9 | int read_int() {
      |     ^~~~~~~~

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