oj.uz

답안 #806834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
806834 2023-08-04T10:21:44 Z Benmath 늑대인간 (IOI18_werewolf) C++14
15 / 100
 1852 ms 27920 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]];
    if(x1<=y1){
    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]++;
    }
    }else{
     int l1=L[i];
    int r1=R[i];
    int ans1=x1;
    int ans2=y1;
    int l=0;
    int r=x1;
    while(l<=r){
    int mid=(l+r)/2;
    int t=querymin(1,0,n-1,mid,x1);
    if(t>=l){
    ans1=min(ans1,mid);
    r=mid-1;
    }else{
    l=mid+1;
    }
    }
    l=y1;
    r=n-1;
    while(l<=r){
    int mid=(l+r)/2;
    int t=querymax(1,0,n-1,y1,mid);
    if(t<=r){
    ans2=max(ans2,mid);
    l=mid+1;
    }else{
    r=mid-1;
    }
    }
    if(ans2>=ans1){
    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:176:9: warning: unused variable 'l1' [-Wunused-variable]
  176 |     int l1=L[i];
      |         ^~
werewolf.cpp:177:9: warning: unused variable 'r1' [-Wunused-variable]
  177 |     int r1=R[i];
      |         ^~
werewolf.cpp:208:10: warning: unused variable 'l1' [-Wunused-variable]
  208 |      int l1=L[i];
      |          ^~
werewolf.cpp:209:9: warning: unused variable 'r1' [-Wunused-variable]
  209 |     int r1=R[i];
      |         ^~
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: 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 2 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 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 212 KB Output is correct
10 Correct 212 ms 640 KB Output is correct
11 Correct 117 ms 628 KB Output is correct
12 Correct 18 ms 596 KB Output is correct
13 Correct 235 ms 636 KB Output is correct
14 Correct 142 ms 628 KB Output is correct
15 Correct 187 ms 724 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 212 KB Output is correct
10 Correct 212 ms 640 KB Output is correct
11 Correct 117 ms 628 KB Output is correct
12 Correct 18 ms 596 KB Output is correct
13 Correct 235 ms 636 KB Output is correct
14 Correct 142 ms 628 KB Output is correct
15 Correct 187 ms 724 KB Output is correct
16 Incorrect 1852 ms 27920 KB Output isn't correct
17 Halted 0 ms 0 KB -