Submission #789678

#	Time	Username	Problem	Language	Result	Execution time	Memory
789678		APROHACK	Werewolf (IOI18_werewolf)	C++17	49 / 100	4043 ms	54500 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define menor 0
#define mayor 1
using namespace std;
int n, m, q;
int rep[200001][2];
vector<pair<int, int> >edjes;
vector<int>adj[200001];
vector<int>linea;
int position[200001];
const int raiz = 450;
vector<vector<int>>divisiones;

int findd(int u, short cual){
	if(rep[u][cual] == u)return u;
	return rep[u][cual] = findd(rep[u][cual], cual);
}

void joinn(int a, int b, short cual){
	a = findd(a, cual);
	b = findd(b, cual);
	
	if(a == b)return ;
	rep[a][cual] = b;
}

void bfs(int u){
	queue<int>cola;
	cola.push(u);
	while(!cola.empty()){
		int cur = cola.front();
		cola.pop();
		linea.pb(cur);
		position[cur] = linea.size()-1;
		for(auto i : adj[cur]){
			if(linea.size() >= 2 and linea[linea.size()-2] == i)continue;
			cola.push(i);
		}
	}
}

struct segTree{
	int minimo, maximo;
	int dd, ht, mid;
	segTree *L, *R;
	segTree(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		if(dd != ht){
			L = new segTree(l, mid);
			R = new segTree(mid + 1 , r);
			minimo = min(L->minimo, R->minimo);
			maximo = max(L->maximo, R->maximo);
		}else{
			minimo = linea[l];
			maximo = linea[l];
		}
	}
	int query(int l, int r, bool cual){
		if ( dd == l and ht == r){
			if( cual == mayor) return maximo;
			return minimo;
		}
		if(r <= mid){
			return L->query(l, r, cual);
		}else if(l > mid){
			return R->query(l, r, cual);
		}else{
			if(cual == mayor){
				return max(L->query(l, mid, cual), R->query(mid+1, r, cual));
			}else{
				return min(L->query(l, mid, cual), R->query(mid+1, r, cual));
			}
		}
	}
	
	
};

segTree *st;

int ver(int s, int pos, bool alreves, int cual){
	if(!alreves){
		int maximo = st->query(position[s], position[s] + pos, cual);
		//cout << " query max " << position[s]  << " to " << position[s]+pos << " = "  << maximo << endl;
		return maximo;
	}else{
		int maximo = st->query(position[s] - pos, position[s], cual);
		//cout << " query max " << position[s] - pos  << " to " << position[s] << " = " << maximo << endl;
		return maximo;
	}
}
bool buscar(int desde,int hasta, int l, int r){
	//cout << "bus " << desde << " " << hasta << endl;
	if(desde > hasta)return false;
	
	while(desde % raiz != 0 and desde <= hasta){
		if(linea[desde] >= l and linea[desde] <= r)return true;
		desde ++ ;
	}
	while((hasta % raiz) !=0 and hasta >= desde){
		if(linea[hasta] >= l and linea[hasta] <= r)return true;
		hasta -- ;
	}
	if(desde > hasta)return false;
	if(desde == hasta)return linea[desde] >= l and linea[desde] <= r;
	if(linea[hasta] >= l and linea[hasta] <= r)return true;
	hasta --;
	for(int i = desde / raiz ; i <= hasta/raiz ; i ++){
		int k = *lower_bound(divisiones[i].begin(), divisiones[i].end(), l);
		if( k >= l and k <= r)return true; 
	}
	return false;
}


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) {
	n = N;
	m = X.size();
	q = S.size();
	int cuenta[N];
	for(int i = 0 ; i < n ; i ++)cuenta[i] = 0;
	for(int i = 0 ; i < m ; i ++){
	  edjes.pb({X[i], Y[i]});
	  cuenta[X[i]] ++;
	  cuenta[Y[i]] ++;
	}
	bool caso = true;
	for(int i = 0 ; i < N ; i ++){
	  if(cuenta[i] > 2)caso = false;
	}
	vector<int>A;
	
	if(!caso){
		  for(int query = 0 ; query < q ; query ++){
			  for(int i = 0 ; i < n ; i ++){
				  rep[i][0] = i;
				  rep[i][1] = i;
				}
			  for(int i = 0 ; i < m ; i ++){
				  if(X[i] <= R[query] and Y[i] <= R[query]){
					  joinn(X[i], Y[i], 0);
				  }
				  if(X[i] >= L[query] and Y[i] >= L[query]){
					  joinn(X[i], Y[i], 1);
				  }
			  }
			  bool posible = false;
			  S[query] = findd(S[query], 1);
			  E[query] = findd(E[query], 0);
			  for(int i = L[query] ; i <= R[query] ; i ++){
				  if(findd(i, 1) == S[query] and findd(i, 0) == E[query]){
					  posible = true;
					  break;
				  }
			  }
			  if(posible)A.pb(1);
			  else A.pb(0);
		  }
	  }else{ // es una linea */
		  int comienzo;
		  for(int i = 0 ; i < N ; i ++){
			  if(cuenta[i] == 1){
				  comienzo = i;
				  break;
			  }
		  }
		  for(int i = 0 ; i < m ; i ++){
			  adj[X[i]].pb(Y[i]);
			  adj[Y[i]].pb(X[i]);
		  }
		  bfs(comienzo);
		  st = new segTree(0, N-1);
		  int ii = 0;
		  vector<int>temporal;
		  while( ii < n){
			  temporal.pb(linea[ii]);
			  ii++;
			  if(ii%raiz == 0){
				  sort(temporal.begin(), temporal.end());
				  divisiones.pb(temporal);
				  temporal.clear();
			  }
		  }
		  
		  
		  for(int query = 0 ; query < q ; query++){
			  //cout << "query " << query << endl;
			  
			  int s = S[query], e = E[query];
			  //cout << s << " " << e << " " << L[query] << " " << R[query] << endl;
			  int mult = 1;
			  bool alreves = false;
			  if(position[s] > position[e]){
				  mult = -1;
				  alreves = true;
			  }
			  int li = 0, ls = max(position[s], position[e]) - min(position[s], position[e]) , pos;
			  //cout << "searching from " << li << " to " << ls << " alreves = " << alreves << endl;
			  pos = (li + ls)/2;
			  while(li+1 < ls){
				  //cout << "asking " << pos << endl;
				  int res = ver(e, pos, !alreves, mayor);
				  if(res > R[query]){
					  ls = pos;
				  }else{
					  li = pos+1;
				  }
				  pos = (li + ls)/2;
			  }
			  int ultimo;
			  if(ver(e, li, !alreves, mayor) > R[query]) ultimo = li;
			  else if(ver(e, ls, !alreves, mayor) > R[query]) ultimo = ls;
			  else ultimo = -1;
			  if(ultimo != -1)ultimo = max(position[s], position[e]) - min(position[s], position[e])-ultimo;
			  /*
			  if(ultimo != -1){
				  ultimo = max(position[s], position[e]) - min(position[s], position[e])-ultimo;
				  cout << "ultimo " << ultimo  << endl;
				  if(!alreves && (position[s]+1 > position[s] + ultimo - 1 or st->query(position[s]+1, position[s]+ultimo-1, menor) >= L[query])){
					  
				  }else if(alreves && (position[s] - ultimo + 1 > position[s]-1 or st->query(position[s] - ultimo+1, position[s]-1, menor) >= L[query])){
				  }else{
					  A.pb(0);
					  continue;
				  }
			  }
			  * */
			  //cout << "es valido " << query << endl;
			  //cout << position[s] << " " << ultimo << endl;
			  
			  li = 1, ls = max(position[s], position[e]) - min(position[s], position[e]) , pos;
			  //cout << "searching from " << li << " to " << ls << " alreves = " << alreves << endl;
			  pos = (li + ls)/2;
			  while(li+1 < ls){
				  //cout << "asking " << pos << endl;
				  int res = ver(s, pos, alreves, menor);
				  if(res < L[query]){
					  ls = pos;
				  }else{
					  li = pos+1;
				  }
				  pos = (li + ls)/2;
			  }
			  int ultimo2 = -1;
			  if(ver(s, li, alreves, menor) < L[query]) ultimo2 = li;
			  else if(ver(s, ls, alreves, menor) < L[query]) ultimo2 = ls;
			  else ultimo2 = -1;
			  //cout << ultimo << " " << ultimo2 << endl;
			  int desde, hasta;
			  
			  if(!alreves){
				  desde = position[s] + ultimo + 1;
				  hasta = position[s] + ultimo2 - 1;	  
				  if(ultimo == -1){
					  desde = position[s];
				  }
				  if(ultimo2 ==-1){
					  hasta = position[e];
				  }
			  }else{
				  hasta = position[s] - ultimo - 1;
				  desde = position[s] - ultimo2 + 1;
				  if(ultimo == -1){
					  hasta = position[s];
				  }
				  if(ultimo2 ==-1){
					  desde = position[e];
				  }
			  }
			  bool ans = buscar(desde, hasta, L[query], R[query]);
			  //cout << "encontrado " << ans << endl;
			  if(ans)A.pb(1);
			  else A.pb(0);
		  }
		  
		  
	  }
  
  return A;
}

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:240:86: warning: right operand of comma operator has no effect [-Wunused-value]
  240 |      li = 1, ls = max(position[s], position[e]) - min(position[s], position[e]) , pos;
      |                                                                                      ^
werewolf.cpp:200:10: warning: variable 'mult' set but not used [-Wunused-but-set-variable]
  200 |      int mult = 1;
      |          ^~~~
werewolf.cpp:180:8: warning: 'comienzo' may be used uninitialized in this function [-Wmaybe-uninitialized]
  180 |     bfs(comienzo);
      |     ~~~^~~~~~~~~~

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