Submission #290228

#	Time	Username	Problem	Language	Result	Execution time	Memory
290228		DanerZein	Werewolf (IOI18_werewolf)	C++14	0 / 100	4072 ms	46744 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;
vector<int> path;
int vis[200010];
ii tree[800010];
void dfs(int u){
  path.push_back(u);
  vis[u]=1;
  for(auto &v: G[u]){
    if(!vis[v]){
      dfs(v);
    }
  }
}
void init(int node,int a,int b){
  if(a>b) return;
  if(a==b){
    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 la,ra,lb,rb;
vector<ii> si;
void query_hu(int node,int a,int b,int x){
  if(a>b) return;
  if(tree[node].first>=x){
    si.push_back(ii(a,b));
    return;
  }
  if(a==b) return;
  int mid=(a+b)/2;
  query_hu(2*node+1,a,mid,x);
  query_hu(2*node+2,mid+1,b,x);
}
void query_wolf(int node,int a,int b,int x){
  if(a>b) return;
  if(tree[node].second<=x){
    si.push_back(ii(a,b));
    return;
  }
  if(a==b) return;
  int mid=(a+b)/2;
  query_wolf(2*node+1,a,mid,x);
  query_wolf(2*node+2,mid+1,b,x);
}
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) {
  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;
  for(int i=0;i<N;i++){
    if(G[i].size()>2){
      sw=1;
    }
    if(G[i].size()==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;
    }
    init(0,0,N-1);
    int q=S.size();
    for(int i=0;i<q;i++){
      la=lb=MAX;
      ra=rb=-MAX;
      sw=0;
      si.clear();
      query_hu(0,0,N-1,L[i]);
      vector<ii>::iterator it=lower_bound(si.begin(),si.end(),ii(m[S[i]],0));
      if(it==si.end()) it--;
      if((*it).first>m[S[i]]) it--;
      la=(*it).first;
      ra=(*it).second;
      int ia,ib;
      ia=ib=it-si.begin();
      bool na,nb;
      na=nb=0;
      while(true){
	if(ib==si.size() and ia==-1) break;
	if(na&nb) break;
        if(ib!=si.size() and nb==0){
	  ib++;
	  if(si[ib].first==ra+1) ra=si[ib].second;
	  else nb=1;
	}
	else nb=1;
	if(ia!=0 and na==0){
	  ia--;
	  if(si[ia].second==la-1) la=si[ia].first;
	  else na=1;
	}
	else na=1;
	//	cout<<la<<" "<<ra<<" "<<nb<<" "<<na<<endl;
      }
      si.clear();
      query_wolf(0,0,N-1,R[i]);
      it=lower_bound(si.begin(),si.end(),ii(m[E[i]],0));
      if(it==si.end()) it--;
      if((*it).first>m[E[i]]) it--;
      lb=(*it).first;
      rb=(*it).second;
      ia=ib=it-si.begin();
      na=nb=0;
      while(true){
	if(ib==si.size() and ia==-1) break;
	if(na&nb) break;
        if(ib!=si.size() and nb==0){
	  ib++;
	  if(si[ib].first==rb+1) rb=si[ib].second;
	  else nb=1;
	}
	else nb=1;
	if(ia!=0 and na==0){
	  ia--;
	  if(si[ia].second==lb-1) lb=si[ia].first;
	  else na=1;
	}
	else na=1;
      }
      //cout<<la<<" "<<ra<<" "<<lb<<" "<<rb<<endl;
      if((la<=lb and ra>=lb) or (la<=rb and ra>=rb)){
	res.push_back(1);
      }
      else{
	res.push_back(0);
      }
    }
    // }
  return res;
}

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:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i=0;i<X.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<path.size();i++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp:136:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  if(ib==si.size() and ia==-1) break;
      |     ~~^~~~~~~~~~~
werewolf.cpp:138:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         if(ib!=si.size() and nb==0){
      |            ~~^~~~~~~~~~~
werewolf.cpp:162:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |  if(ib==si.size() and ia==-1) break;
      |     ~~^~~~~~~~~~~
werewolf.cpp:164:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         if(ib!=si.size() and nb==0){
      |            ~~^~~~~~~~~~~
werewolf.cpp:86:8: warning: variable 'sw' set but not used [-Wunused-but-set-variable]
   86 |   bool sw=0;
      |        ^~
werewolf.cpp:114:8: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     dfs(id);
      |     ~~~^~~~

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