oj.uz

Submission #144006

# Submission time Handle Problem Language Result Execution time Memory
144006 2019-08-15T16:11:57 Z Minnakhmetov Werewolf (IOI18_werewolf) C++14
100 / 100
 987 ms 135180 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 4e5 + 5, L = 20;
int w[N], tin[2][N], tout[2][N], p[2][N][L], t[N];
vector<int> g[N], tr[2][N];
int timer;

struct E {
	int t, x, y, i, k;
};

void upd(int x, int y) {
	for (; x < N; x |= x + 1)
		t[x] += y;
}

int que(int x) {
	int s = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		s += t[x];
	return s;
}

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

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

	if (a != b) {
		w[a] += w[b];
    	w[b] = a;
    	tr[type][a].push_back(b);
	}
}

void dfs(int node, int p[N][L], int tin[N], int tout[N], vector<int> tr[N]) {
	tin[node] = ++timer;
	for (int i = 1; i < L; i++) {
		p[node][i] = p[p[node][i - 1]][i - 1];
	}
	for (int to : tr[node]) {
		p[to][0] = node;
		dfs(to, p, tin, tout, tr);
	}
	tout[node] = timer;
}

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++) {
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}

	fill(w, w + n, -1);

	for (int i = n - 1; i >= 0; i--) {
		for (int to : g[i]) {
			if (to > i) {
				connect(i, to, 0);
			}
		}
	}

	fill(w, w + n, -1);

	for (int i = 0; i < n; i++) {
		for (int to : g[i]) {
			if (to < i) {
				connect(i, to, 1);
			}
		}
	}

	timer = -1;
	dfs(0, p[0], tin[0], tout[0], tr[0]);

	timer = -1;
	fill(p[1][n - 1], p[1][n - 1] + L, n - 1);
	dfs(n - 1, p[1], tin[1], tout[1], tr[1]);

	vector<E> ev;

	for (int i = 0; i < q; i++) {
		int v1 = s[i], v2 = e[i];

		for (int j = L - 1; j >= 0; j--) {
			if (p[0][v1][j] >= l[i]) {
				v1 = p[0][v1][j];
			}
		}

		for (int j = L - 1; j >= 0; j--) {
			if (p[1][v2][j] <= r[i]) {
				v2 = p[1][v2][j];
			}
		}

		ev.push_back({ tout[0][v1], tin[1][v2], tout[1][v2], i, 1 });
		ev.push_back({ tin[0][v1] - 1, tin[1][v2], tout[1][v2], i, -1 });
	}

	for (int i = 0; i < n; i++) {
		ev.push_back({ tin[0][i], tin[1][i], -1, -1 });
	}

	sort(all(ev), [](E a, E b) {
		return a.t == b.t ? a.i == -1 : a.t < b.t;
	});

	for (E e : ev) {
		if (e.i == -1) {
			upd(e.x, 1);
		}
		else {
			ans[e.i] += (que(e.y) - que(e.x - 1)) * e.k;
		}
	}

	for (int i = 0; i < q; i++)
		ans[i] = ans[i] > 0;

  	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 28 ms 28664 KB Output is correct
6 Correct 28 ms 28792 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 28 ms 28664 KB Output is correct
9 Correct 28 ms 28668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 28 ms 28664 KB Output is correct
6 Correct 28 ms 28792 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 28 ms 28664 KB Output is correct
9 Correct 28 ms 28668 KB Output is correct
10 Correct 36 ms 30000 KB Output is correct
11 Correct 36 ms 29900 KB Output is correct
12 Correct 36 ms 29912 KB Output is correct
13 Correct 35 ms 30168 KB Output is correct
14 Correct 35 ms 30044 KB Output is correct
15 Correct 37 ms 30040 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 109264 KB Output is correct
2 Correct 776 ms 123572 KB Output is correct
3 Correct 712 ms 119776 KB Output is correct
4 Correct 838 ms 118112 KB Output is correct
5 Correct 710 ms 118008 KB Output is correct
6 Correct 748 ms 117840 KB Output is correct
7 Correct 727 ms 117724 KB Output is correct
8 Correct 724 ms 123472 KB Output is correct
9 Correct 622 ms 119604 KB Output is correct
10 Correct 606 ms 118120 KB Output is correct
11 Correct 620 ms 117888 KB Output is correct
12 Correct 647 ms 118028 KB Output is correct
13 Correct 788 ms 129732 KB Output is correct
14 Correct 818 ms 129800 KB Output is correct
15 Correct 807 ms 129864 KB Output is correct
16 Correct 821 ms 129736 KB Output is correct
17 Correct 730 ms 117716 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 28 ms 28664 KB Output is correct
6 Correct 28 ms 28792 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 28 ms 28664 KB Output is correct
9 Correct 28 ms 28668 KB Output is correct
10 Correct 36 ms 30000 KB Output is correct
11 Correct 36 ms 29900 KB Output is correct
12 Correct 36 ms 29912 KB Output is correct
13 Correct 35 ms 30168 KB Output is correct
14 Correct 35 ms 30044 KB Output is correct
15 Correct 37 ms 30040 KB Output is correct
16 Correct 764 ms 109264 KB Output is correct
17 Correct 776 ms 123572 KB Output is correct
18 Correct 712 ms 119776 KB Output is correct
19 Correct 838 ms 118112 KB Output is correct
20 Correct 710 ms 118008 KB Output is correct
21 Correct 748 ms 117840 KB Output is correct
22 Correct 727 ms 117724 KB Output is correct
23 Correct 724 ms 123472 KB Output is correct
24 Correct 622 ms 119604 KB Output is correct
25 Correct 606 ms 118120 KB Output is correct
26 Correct 620 ms 117888 KB Output is correct
27 Correct 647 ms 118028 KB Output is correct
28 Correct 788 ms 129732 KB Output is correct
29 Correct 818 ms 129800 KB Output is correct
30 Correct 807 ms 129864 KB Output is correct
31 Correct 821 ms 129736 KB Output is correct
32 Correct 730 ms 117716 KB Output is correct
33 Correct 819 ms 118788 KB Output is correct
34 Correct 406 ms 70568 KB Output is correct
35 Correct 886 ms 122872 KB Output is correct
36 Correct 858 ms 118932 KB Output is correct
37 Correct 863 ms 121720 KB Output is correct
38 Correct 836 ms 119676 KB Output is correct
39 Correct 878 ms 134768 KB Output is correct
40 Correct 987 ms 130128 KB Output is correct
41 Correct 829 ms 121040 KB Output is correct
42 Correct 702 ms 118864 KB Output is correct
43 Correct 928 ms 129108 KB Output is correct
44 Correct 817 ms 121700 KB Output is correct
45 Correct 770 ms 135180 KB Output is correct
46 Correct 765 ms 134844 KB Output is correct
47 Correct 847 ms 129916 KB Output is correct
48 Correct 842 ms 129740 KB Output is correct
49 Correct 834 ms 129944 KB Output is correct
50 Correct 822 ms 129868 KB Output is correct
51 Correct 930 ms 130100 KB Output is correct
52 Correct 932 ms 130072 KB Output is correct