oj.uz

답안 #806829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806829 2023-08-04T10:10:22 Z Benmath 늑대인간 (IOI18_werewolf) C++14
15 / 100
 1635 ms 32052 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+1,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+1,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=x1;
    int ans2=y1;
    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:171:9: warning: unused variable 'x' [-Wunused-variable]
  171 |     int x=S[i];
      |         ^
werewolf.cpp:172:9: warning: unused variable 'y' [-Wunused-variable]
  172 |     int y=E[i];
      |         ^
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 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 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 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 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 234 ms 748 KB Output is correct
11 Correct 118 ms 724 KB Output is correct
12 Correct 15 ms 724 KB Output is correct
13 Correct 234 ms 748 KB Output is correct
14 Correct 144 ms 736 KB Output is correct
15 Correct 187 ms 864 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1635 ms 32052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 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 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 234 ms 748 KB Output is correct
11 Correct 118 ms 724 KB Output is correct
12 Correct 15 ms 724 KB Output is correct
13 Correct 234 ms 748 KB Output is correct
14 Correct 144 ms 736 KB Output is correct
15 Correct 187 ms 864 KB Output is correct
16 Incorrect 1635 ms 32052 KB Output isn't correct
17 Halted 0 ms 0 KB -