Submission #141293

#	Time	Username	Problem	Language	Result	Execution time	Memory
141293		Minnakhmetov	Werewolf (IOI18_werewolf)	C++14	15 / 100	634 ms	22544 KiB

werewolf

#include "werewolf.h"

using namespace std;

#define ll long long

const int N = 2e5 + 5;
int w[N];

int findSet(int v) {
	return w[v] < 0 ? v : w[v] = findSet(w[v]);
}

void connect(int a, int b) {
	a = findSet(a);
	b = findSet(b);

	if (a != b) {
		if (w[a] > w[b])
			swap(a, b);
		w[a] += w[b];
		w[b] = a;
	}
}

vector<int> check_validity(int n, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {

  	int q = s.size(), m = x.size();
  	vector<int> ans(q);

  	for (int i = 0; i < m; i++) {
  		if (x[i] > y[i]) {
  			swap(x[i], y[i]);
  		}
  	}

  	for (int i = 0; i < q; i++) {
  		fill(w, w + n + n, -1);

  		for (int j = 0; j < m; j++) {
  			if (x[j] >= l[i])
  				connect(x[j], y[j]);
  			if (y[j] <= r[i])
  				connect(x[j] + n, y[j] + n);
  		}

  		for (int j = l[i]; j <= r[i]; j++) {
  			if (findSet(s[i]) == findSet(j) && findSet(e[i] + n) == findSet(j + n)) {
  				ans[i] = 1;
  				break;
  			}
  		}
  	}

  	return ans;
}

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