oj.uz

Submission #789678

# Submission time Handle Problem Language Result Execution time Memory
789678 2023-07-21T17:56:00 Z APROHACK Werewolf (IOI18_werewolf) C++17
49 / 100
 4000 ms 54500 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 288 ms 5336 KB Output is correct
11 Correct 229 ms 5340 KB Output is correct
12 Correct 12 ms 5716 KB Output is correct
13 Correct 270 ms 5336 KB Output is correct
14 Correct 205 ms 5332 KB Output is correct
15 Correct 532 ms 5460 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1881 ms 46004 KB Output is correct
2 Correct 1937 ms 54332 KB Output is correct
3 Correct 2012 ms 54500 KB Output is correct
4 Correct 1849 ms 54316 KB Output is correct
5 Correct 1826 ms 54352 KB Output is correct
6 Correct 1787 ms 54332 KB Output is correct
7 Correct 1762 ms 54380 KB Output is correct
8 Correct 1813 ms 54400 KB Output is correct
9 Correct 600 ms 54428 KB Output is correct
10 Correct 750 ms 54332 KB Output is correct
11 Correct 915 ms 54396 KB Output is correct
12 Correct 907 ms 54332 KB Output is correct
13 Correct 1894 ms 54360 KB Output is correct
14 Correct 1895 ms 54392 KB Output is correct
15 Correct 1764 ms 54384 KB Output is correct
16 Correct 1791 ms 54484 KB Output is correct
17 Correct 1807 ms 54400 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 288 ms 5336 KB Output is correct
11 Correct 229 ms 5340 KB Output is correct
12 Correct 12 ms 5716 KB Output is correct
13 Correct 270 ms 5336 KB Output is correct
14 Correct 205 ms 5332 KB Output is correct
15 Correct 532 ms 5460 KB Output is correct
16 Correct 1881 ms 46004 KB Output is correct
17 Correct 1937 ms 54332 KB Output is correct
18 Correct 2012 ms 54500 KB Output is correct
19 Correct 1849 ms 54316 KB Output is correct
20 Correct 1826 ms 54352 KB Output is correct
21 Correct 1787 ms 54332 KB Output is correct
22 Correct 1762 ms 54380 KB Output is correct
23 Correct 1813 ms 54400 KB Output is correct
24 Correct 600 ms 54428 KB Output is correct
25 Correct 750 ms 54332 KB Output is correct
26 Correct 915 ms 54396 KB Output is correct
27 Correct 907 ms 54332 KB Output is correct
28 Correct 1894 ms 54360 KB Output is correct
29 Correct 1895 ms 54392 KB Output is correct
30 Correct 1764 ms 54384 KB Output is correct
31 Correct 1791 ms 54484 KB Output is correct
32 Correct 1807 ms 54400 KB Output is correct
33 Execution timed out 4043 ms 26848 KB Time limit exceeded
34 Halted 0 ms 0 KB -