제출 #297650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297650		DanerZein	늑대인간 (IOI18_werewolf)	C++14	0 / 100	574 ms	116716 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
int l,r;
bitset<200010> vh,vw;
vector<vi> G;
void dfs_human(int u){
  if(u<l) return;
  vh[u]=1;
  for(auto &v:G[u]){
    if(!vh[v]){
      dfs_human(v);
    }
  }
}
void dfs_wolf(int u){
  if(u>r) return;
  vw[u]=1;
  for(auto &v:G[u]){
    if(!vw[v]){
      dfs_wolf(v);
    }
  }
}
map<int,int> m,mtr;
vector<int> path;
int vis[800010];
ii tree[800010];
void dfs(int u){
  path.push_back(u);
  vis[u]=1;
  for(auto &v: G[u]){
    if(!vis[v]){
      dfs(v);
    }
  }
}
int le[800010];
void init(int node,int a,int b){
  if(a>b) return;
  if(a==b){
    mtr[a]=node;
    le[node]=a;
    tree[node]=ii(path[a],path[a]);
    return;
  }
  int mid=(a+b)/2;
  init(2*node+1,a,mid);
  init(2*node+2,mid+1,b);
  tree[node].first=min(tree[2*node+1].first,tree[2*node+2].first);
  tree[node].second=max(tree[2*node+1].second,tree[2*node+2].second);
}
int find_left(int node,int l,int r){
  while(node>0 and (~node&1 or node-- and l<=tree[node].first and tree[node].second<=r)){
    if(node%2==0){
      node/=2;
      //node--;
    }
    else node/=2;
  }
  if(node==0 and tree[node].first>=l and tree[node].second<=r) return 0;
  node=2*node+1;
  while(le[node]==-1){
    if(tree[2*node+2].first>=l and tree[2*node+2].second<=r) node=2*node+1;
    else node=2*node+2;
  }
  if(tree[node].first>=l and tree[node].second<=r)
  return le[node];
  else return le[node]+1;
}
int M;
int find_right(int node,int l,int r){
  while(node>0 and (~node&1 or node-- and l<=tree[node].first and tree[node].second<=r)){
    if(node%2==0){
      node/=2;
      // node--;
    }
    else node/=2;
  }
  if(node==0 and tree[node].first>=l and tree[node].second<=r) return M;
  node=2*node+2;
  while(le[node]==-1){
    if(tree[2*node+1].first>=l and tree[2*node+1].second<=r) node=2*node+2;
    else node=2*node+1;
  }
  if(tree[node].first>=l and tree[node].second<=r)
  return le[node];
  else return le[node]-1;
}
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 aux=~5;
  /*for(int i=0;i<3;i++){
    if((aux&(1<<i))!=0) cout<<"1";
    else cout<<"0";
  }
  cout<<endl;*/
  M=N-1;
  G.resize(N+1);
  for(int i=0;i<X.size();i++){
    int u=X[i],v=Y[i];
    G[u].push_back(v);
    G[v].push_back(u);
  }
  bool sw=0;
  int id=-1;
  for(int i=0;i<N;i++){
    if(G[i].size()>2){
      sw=1;
    }
    if(G[i].size()==1 and id==-1) id=i;
  }
  vector<int> res;
   if(sw==1){
    for(int i=0;i<S.size();i++){
      l=L[i];
      r=R[i];
      vh.reset();
      vw.reset();
      dfs_human(S[i]);
      dfs_wolf(E[i]);
      bool sw=0;
      for(int i=0;i<N;i++){
	if(vh[i]==1 and vw[i]==1){
	  sw=1;
	  break;
	}
      }
      res.push_back(sw);
    }
    }
   else{
     dfs(id);
     for(int i=0;i<path.size();i++){
       m[path[i]]=i;
     }
     memset(le,-1,sizeof le);
     init(0,0,N-1);
     int q=S.size();
     for(int i=0;i<q;i++){
       int ns,ne,ra,lb,rb,la;
       ns=mtr[m[S[i]]];
       ne=mtr[m[E[i]]];
       la=find_left(ns,L[i],N);
       ra=find_right(ns,L[i],N);
       lb=find_left(ne,0,R[i]);
       rb=find_right(ne,0,R[i]);
       if(la>ra) swap(la,ra);
       if(lb>rb) swap(lb,rb);
       // cout<<la<<" "<<ra<<" "<<lb<<" "<<rb<<" "<<ns<<" "<<ne<<endl;
       if((la<=lb and lb<=ra) or (la<=rb and rb<=ra)) res.push_back(1);
      else res.push_back(0);
     }
   }
   return res;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'int find_left(int, int, int)':
werewolf.cpp:57:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   57 |   while(node>0 and (~node&1 or node-- and l<=tree[node].first and tree[node].second<=r)){
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'int find_right(int, int, int)':
werewolf.cpp:76:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   76 |   while(node>0 and (~node&1 or node-- and l<=tree[node].first and tree[node].second<=r)){
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i=0;i<X.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |      for(int i=0;i<path.size();i++){
      |                  ~^~~~~~~~~~~~
werewolf.cpp:96:7: warning: unused variable 'aux' [-Wunused-variable]
   96 |   int aux=~5;
      |       ^~~

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