oj.uz

Submission #806815

# Submission time Handle Problem Language Result Execution time Memory
806815 2023-08-04T10:03:42 Z Benmath Werewolf (IOI18_werewolf) C++14
15 / 100
 1887 ms 25944 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 222 ms 752 KB Output is correct
11 Correct 148 ms 740 KB Output is correct
12 Correct 17 ms 752 KB Output is correct
13 Correct 252 ms 752 KB Output is correct
14 Correct 205 ms 744 KB Output is correct
15 Correct 201 ms 848 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 312 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 222 ms 752 KB Output is correct
11 Correct 148 ms 740 KB Output is correct
12 Correct 17 ms 752 KB Output is correct
13 Correct 252 ms 752 KB Output is correct
14 Correct 205 ms 744 KB Output is correct
15 Correct 201 ms 848 KB Output is correct
16 Incorrect 1887 ms 25944 KB Output isn't correct
17 Halted 0 ms 0 KB -