Submission #788184

#	Time	Username	Problem	Language	Result	Execution time	Memory
788184		APROHACK	Werewolf (IOI18_werewolf)	C++17	15 / 100	4014 ms	21368 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m, q;
int rep[200001][2];
vector<pair<int, int> >edjes;

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;
	
}



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();
  for(int i = 0 ; i < m ; i ++){
	  edjes.pb({X[i], Y[i]});
  }
  vector<int>A;
  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);
  }
  
  return A;
}

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