oj.uz

Submission #99208

# Submission time Handle Problem Language Result Execution time Memory
99208 2019-03-01T17:50:02 Z eriksuenderhauf Werewolf (IOI18_werewolf) C++11
15 / 100
 4000 ms 125688 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 50;
vi adj[MAXN], ltree[MAXN], rtree[MAXN], lArr[MAXN], rArr[MAXN];
int par[MAXN], sz[MAXN], lA[MAXN], rA[MAXN], ind[MAXN];
int stL[MAXN], enL[MAXN], stR[MAXN], enR[MAXN];
int lPar[20][MAXN], rPar[20][MAXN];
set<int> comp[MAXN];
int n, m, q, t, BIT[MAXN], tmp[2*MAXN];

void add(int ind, int v) {
	ind++;
	while (ind < MAXN) {
		BIT[ind] += v;
		ind += ind & -ind;
	}
}

int sum(int ind) {
	ind++;
	int ret = 0;
	while (ind > 0) {
		ret += BIT[ind];
		ind -= ind & -ind;
	}
	return ret;
}

void ldfs(int u, int p) {
	stL[u] = t;
	lA[t++] = u;
	for (int v: ltree[u])
		if (v != p) {
			ldfs(v, u);
			lPar[0][v] = u;
		}
	enL[u] = t - 1;
}

void rdfs(int u, int p) {
	stR[u] = t;
	rA[t++] = u;
	for (int v: rtree[u])
		if (v != p) {
			rdfs(v, u);
			rPar[0][v] = u;
		}
	enR[u] = t - 1;
}

int qry(int x) {
	return x == par[x] ? x : par[x] = qry(par[x]);
}

void join(int x, int y) {
	x = qry(x), y = qry(y);
	if (x == y) return;
	if (sz[x] > sz[y]) swap(x, y);
	par[x] = y;
	sz[y] += sz[x];
	comp[y].insert(comp[x].begin(), comp[x].end());
	comp[x].clear();
}

void init() {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
		comp[i] = {i};
	}
}

vi check_validity(int N, vi x, vi y, vi s, vi e, vi l, vi r) {
	n = N, m = x.size(), q = l.size();
	for (int i = 0; i < m; i++) {
		adj[x[i]].pb(y[i]);
		adj[y[i]].pb(x[i]);
	}
	init();
	for (int i = 0; i < n; i++) { // r
		for (int v: adj[i]) {
			if (v > i || qry(i) == qry(v)) continue;
			int u = *(--comp[qry(v)].end());
			join(i, u);
			rtree[i].pb(u);
			rtree[u].pb(i);
		}
	}
	init();
	for (int i = n - 1; i >= 0; i--) { // l
		for (int v: adj[i]) {
			if (v < i || qry(i) == qry(v)) continue;
			int u = *(comp[qry(v)].begin());
			join(i, u);
			ltree[i].pb(u);
			ltree[u].pb(i);
		}
	}
	for (int i = 0; i < 20; i++)
		fill(lPar[i], lPar[i] + MAXN, 0), fill(rPar[i], rPar[i] + MAXN, n - 1);
	t = 0;
	ldfs(0, -1);
	t = 0;
	rdfs(n - 1, -1);
	for (int i = 1; i < 20; i++)
		for (int j = 0; j < n; j++)
			lPar[i][j] = lPar[i - 1][lPar[i - 1][j]],
			rPar[i][j] = rPar[i - 1][rPar[i - 1][j]];
	for (int i = 0; i < n; i++)
		ind[rA[i]] = i;
	vi ret;
	for (int i = 0; i < q; i++) {
		ret.pb(0);
		int u = s[i];
		for (int j = 19; j >= 0; j--)
			if (lPar[j][u] >= l[i])
				u = lPar[j][u];
		lArr[stL[u]].pb(i);
		rArr[enL[u]].pb(i);
	}
	for (int i = 0; i < n; i++) {
		for (int j: lArr[i]) {
			int u = e[j];
			for (int k = 19; k >= 0; k--)
				if (rPar[k][u] <= r[j])
					u = rPar[k][u];
			tmp[j] = sum(enR[u]) - sum(stR[u] - 1);
		}
		add(ind[lA[i]], 1);
		for (int j: rArr[i]) {
			int u = e[j];
			for (int k = 19; k >= 0; k--)
				if (rPar[k][u] <= r[j])
					u = rPar[k][u];
			if (sum(enR[u]) - sum(stR[u] - 1) != tmp[j])
				ret[j] = 1;
			else
				ret[j] = 0;
		}
	}
	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 64676 KB Output is correct
2 Correct 60 ms 64604 KB Output is correct
3 Correct 60 ms 64636 KB Output is correct
4 Correct 67 ms 64608 KB Output is correct
5 Correct 85 ms 64648 KB Output is correct
6 Correct 70 ms 64680 KB Output is correct
7 Correct 65 ms 64632 KB Output is correct
8 Correct 71 ms 64692 KB Output is correct
9 Correct 66 ms 64688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 64676 KB Output is correct
2 Correct 60 ms 64604 KB Output is correct
3 Correct 60 ms 64636 KB Output is correct
4 Correct 67 ms 64608 KB Output is correct
5 Correct 85 ms 64648 KB Output is correct
6 Correct 70 ms 64680 KB Output is correct
7 Correct 65 ms 64632 KB Output is correct
8 Correct 71 ms 64692 KB Output is correct
9 Correct 66 ms 64688 KB Output is correct
10 Correct 86 ms 65568 KB Output is correct
11 Correct 82 ms 65524 KB Output is correct
12 Correct 76 ms 65540 KB Output is correct
13 Correct 80 ms 65724 KB Output is correct
14 Correct 167 ms 65860 KB Output is correct
15 Correct 73 ms 65628 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 125688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 64676 KB Output is correct
2 Correct 60 ms 64604 KB Output is correct
3 Correct 60 ms 64636 KB Output is correct
4 Correct 67 ms 64608 KB Output is correct
5 Correct 85 ms 64648 KB Output is correct
6 Correct 70 ms 64680 KB Output is correct
7 Correct 65 ms 64632 KB Output is correct
8 Correct 71 ms 64692 KB Output is correct
9 Correct 66 ms 64688 KB Output is correct
10 Correct 86 ms 65568 KB Output is correct
11 Correct 82 ms 65524 KB Output is correct
12 Correct 76 ms 65540 KB Output is correct
13 Correct 80 ms 65724 KB Output is correct
14 Correct 167 ms 65860 KB Output is correct
15 Correct 73 ms 65628 KB Output is correct
16 Execution timed out 4054 ms 125688 KB Time limit exceeded
17 Halted 0 ms 0 KB -