oj.uz

Submission #1029762

# Submission time Handle Problem Language Result Execution time Memory
1029762 2024-07-21T09:38:40 Z DorostWef Werewolf (IOI18_werewolf) C++17
0 / 100
 581 ms 143556 KB 
/* In the name of GOD */

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
const int N = 200012;
vector <int> g[N], t[2][N * 2];
int p[N * 2];
int par[2][N * 2];
int q;
int n;
int m;
int sz = N;
bool vis[N * 2];

void clear () {
	sz = N;
	for (int i = 0; i < N * 2; i++) 
		p[i] = i;
}

int get_par (int v) {
	return (p[v] == v ? v : p[v] = get_par (p[v]));
}

void merge (int u, int v, int i) {
	u = get_par (u);
	v = get_par (v);
	if (u == v)
		return;
	sz++;
	p[u] = sz;
	p[v] = sz;
	t[i][sz].push_back(v);
	t[i][sz].push_back(u);
}

struct que {
	int s, e, l, r;
	int v1, v2;
} qu[N];

vector <int> ll[N], rr[N];
int st [2][N * 2], ft [2][N * 2];
int ti = 1;

void dfs (int v, int i) {
	vis[v] = true;
	st[i][v] = ti;
	for (int u : t[i][v])
		dfs (u, i);
	if (v < N)
		ti++;
	ft[i][v] = ti;
}

const int SegN = N * 4;
vector <int> seg[SegN];
int aa[N];

void build (int v = 1, int tl = 0, int tr = n - 1) {
	if (tl == tr) {
		seg[v] = {aa[tl]};
		return;
	}
	int mid = (tl + tr) >> 1;
	build (v << 1, tl, mid);
	build (v << 1 | 1, mid + 1, tr);
	merge(seg[v << 1].begin(), seg[v << 1].end(), seg[v << 1 | 1].begin(), seg[v << 1 | 1].end(), back_inserter(seg[v]));
}

int get (int l, int r, int s, int e, int v = 1, int tl = 0, int tr = n - 1) {
	if (l > tr || tl > r)
		return 0;
	if (l <= tl && tr <= r) {
		if (lower_bound(seg[v].begin(), seg[v].end(), s) == upper_bound (seg[v].begin(), seg[v].end(), e)) {
			return 0;
		}
		return 1;
	}
	int mid = (tl + tr) >> 1;
	return get (l, r, s, e, v << 1, tl, mid) | get (l, r, s, e, v << 1 | 1, mid + 1, tr);
}

std::vector<int> check_validity(int NN, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    q = S.size();
    n = NN;
    m = X.size();
	for (int i = 0; i < m; i++) {
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for (int i = 0; i < q; i++) {
		qu[i].s = S[i];
		qu[i].e = E[i];
		qu[i].l = L[i];
		qu[i].r = R[i];
		ll[L[i]].push_back(i);
		rr[R[i]].push_back(i);
	}
	clear();
	for (int i = 0; i < n; i++) {
		for (int j : g[i]) {
			if (j < i)
				merge (i, j, 0);
		}
		for (int j : rr[i]) {
			qu[j].v1 = get_par (qu[j].e);
		}
	}
	clear();
	for (int i = n - 1; i >= 0; i--) {
		for (int j : g[i]) 
			if (j > i)
				merge (i, j, 1);
		for (int j : ll[i]) {
			qu[j].v2 = get_par (qu[j].s);
		}
	}
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[0][i].empty()) {
			dfs (i, 0);
		}
	}
	ti = 1;
	for (int i = 0; i < 2 * N; i++)
		vis[i] = false;
	for (int i = 2 * N - 1; i >= N; i--) {
		if (!vis[i] && !t[1][i].empty()) {
			dfs (i, 1);
		}
	}
	for (int i = 0; i < 2 * N; i++) {
		ft[0][i]--;
		ft[1][i]--;
	}
	for (int i = 0; i < n; i++)
		aa[st[0][i]] = st[1][i];
	build ();
	vector <int> wef;
	for (int i = 0; i < q; i++) {
		wef.push_back(get (st[0][qu[i].v1], ft[0][qu[i].v1], st[1][qu[i].v2], ft[1][qu[i].v2]));
	}
	return wef;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57176 KB Output is correct
2 Correct 25 ms 57436 KB Output is correct
3 Correct 24 ms 57256 KB Output is correct
4 Incorrect 28 ms 57180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57176 KB Output is correct
2 Correct 25 ms 57436 KB Output is correct
3 Correct 24 ms 57256 KB Output is correct
4 Incorrect 28 ms 57180 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 136900 KB Output is correct
2 Correct 581 ms 143332 KB Output is correct
3 Correct 497 ms 139368 KB Output is correct
4 Correct 573 ms 137416 KB Output is correct
5 Correct 545 ms 137436 KB Output is correct
6 Correct 508 ms 137412 KB Output is correct
7 Correct 411 ms 134856 KB Output is correct
8 Correct 520 ms 143556 KB Output is correct
9 Correct 474 ms 138308 KB Output is correct
10 Incorrect 353 ms 136136 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57176 KB Output is correct
2 Correct 25 ms 57436 KB Output is correct
3 Correct 24 ms 57256 KB Output is correct
4 Incorrect 28 ms 57180 KB Output isn't correct
5 Halted 0 ms 0 KB -