oj.uz

Submission #382302

# Submission time Handle Problem Language Result Execution time Memory
382302 2021-03-27T02:26:01 Z luciocf Werewolf (IOI18_werewolf) C++14
100 / 100
 1260 ms 204004 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int maxn = 6e5+10;

int n;

struct Edge
{
	int u, v, w;
} edge[2][maxn];

struct DSU
{
	int pai[maxn];

	void init(void)
	{
		for (int i = 1; i < maxn; i++)
			pai[i] = i;
	}

	int Find(int x)
	{
		if (pai[x] == x) return x;
		return pai[x] = Find(pai[x]);
	}

	void Join(int x, int y)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;

		pai[y] = x;
	}
} dsu;

struct BIT
{
	int bit[maxn];

	void upd(int x, int v)
	{
		for (; x < maxn; x += (x&-x))
			bit[x] += v;
	}

	int soma(int x)
	{
		int ans = 0;
		for (; x > 0; x -= (x&-x))
			ans += bit[x];
		return ans;
	}

	int get(int l, int r)
	{
		return soma(r) - soma(l-1);
	}
} BIT;

struct Event
{
	int x, y1, y2, t, ind;

	bool operator <(const Event &o)
	{
		if (o.x == x) return t < o.t;
		return x < o.x;
	}
} event[maxn];

int val[2][maxn];

int st[2][maxn], en[2][maxn], tt;

int tab[2][maxn][20];

int ans[maxn];

vector<int> grafo[2][maxn];

void dfs(int u, int p, int q)
{
	st[q][u] = ++tt;

	for (auto v: grafo[q][u])
	{
		if (v != p)
		{
			tab[q][v][0] = u;

			dfs(v, u, q);
		}
	}

	en[q][u] = tt;
}

void build_tab(int q)
{
	for (int j = 1; j < 20; j++)
		for (int i = 1; i < maxn; i++)
			tab[q][i][j] = tab[q][tab[q][i][j-1]][j-1];
}

int get_menor(int u, int k)
{
	for (int i = 19; i >= 0; i--)
		if (val[0][tab[0][u][i]] >= k)
			u = tab[0][u][i];

	return u;
}

int get_maior(int u, int k)
{
	for (int i = 19; i >= 0; i--)
		if (tab[1][u][i] && val[1][tab[1][u][i]] <= k)
			u = tab[1][u][i];

	return u;
}

void build(int q, int m)
{
	dsu.init();

	int ind = n;

	for (int i = 1; i <= m; i++)
	{
		int u = dsu.Find(edge[q][i].u), v = dsu.Find(edge[q][i].v), w = edge[q][i].w;

		if (u != v)
		{
			++ind;
			val[q][ind] = w;

			dsu.Join(ind, u); dsu.Join(ind, v);

			grafo[q][ind].push_back(u); grafo[q][u].push_back(ind);
			grafo[q][ind].push_back(v); grafo[q][v].push_back(ind);
		}
	}

	tt = 0;
	dfs(dsu.Find(1), 0, q);
	build_tab(q);
}

void do_sweep(int q)
{
	sort(event+1, event+q+1);

	for (int i = 1; i <= q; i++)
	{
		auto E = event[i];

		if (E.t == 0) BIT.upd(E.y1, 1);
		else ans[E.ind] += (E.t == 1 ? -1 : 1)*BIT.get(E.y1, E.y2);
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
								vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R)
{
	n = N;
	int m = 0;

	for (int i = 0; i < X.size(); i++)
	{
		edge[0][++m] = {X[i]+1, Y[i]+1, min(X[i]+1, Y[i]+1)};
		edge[1][m] = {X[i]+1, Y[i]+1, max(X[i]+1, Y[i]+1)};
	}

	sort(edge[0]+1, edge[0]+m+1, [&] (Edge a, Edge b) {return a.w > b.w;});
	build(0, m);

	sort(edge[1]+1, edge[1]+m+1, [&] (Edge a, Edge b) {return a.w < b.w;});
	build(1, m);

	int queries = 0;

	for (int i = 0; i < S.size(); i++)
	{
		int s = S[i]+1, e = E[i]+1, l = L[i]+1, r = R[i]+1;

		int u = get_menor(s, l);
		int v = get_maior(e, r);

		event[++queries] = {st[0][u]-1, st[1][v], en[1][v], 1, i+1};
		event[++queries] = {en[0][u], st[1][v], en[1][v], 2, i+1};
	}

	for (int i = 1; i <= n; i++)
		event[++queries] = {st[0][i], st[1][i], st[1][i], 0, 0};

	do_sweep(queries);

	vector<int> final;

	for (int i = 1; i <= S.size(); i++)
		final.push_back(ans[i] > 0);

	return final;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:174:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |  for (int i = 0; i < X.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:188:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |  for (int i = 0; i < S.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:206:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |  for (int i = 1; i <= S.size(); i++)
      |                  ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 124908 KB Output is correct
2 Correct 272 ms 124908 KB Output is correct
3 Correct 265 ms 124908 KB Output is correct
4 Correct 275 ms 124908 KB Output is correct
5 Correct 261 ms 125036 KB Output is correct
6 Correct 261 ms 124908 KB Output is correct
7 Correct 258 ms 125036 KB Output is correct
8 Correct 265 ms 124952 KB Output is correct
9 Correct 257 ms 124928 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 124908 KB Output is correct
2 Correct 272 ms 124908 KB Output is correct
3 Correct 265 ms 124908 KB Output is correct
4 Correct 275 ms 124908 KB Output is correct
5 Correct 261 ms 125036 KB Output is correct
6 Correct 261 ms 124908 KB Output is correct
7 Correct 258 ms 125036 KB Output is correct
8 Correct 265 ms 124952 KB Output is correct
9 Correct 257 ms 124928 KB Output is correct
10 Correct 265 ms 126060 KB Output is correct
11 Correct 273 ms 126060 KB Output is correct
12 Correct 281 ms 125932 KB Output is correct
13 Correct 264 ms 126060 KB Output is correct
14 Correct 280 ms 126188 KB Output is correct
15 Correct 266 ms 126060 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 187160 KB Output is correct
2 Correct 1119 ms 195940 KB Output is correct
3 Correct 998 ms 190924 KB Output is correct
4 Correct 987 ms 188576 KB Output is correct
5 Correct 974 ms 188388 KB Output is correct
6 Correct 1058 ms 188132 KB Output is correct
7 Correct 1069 ms 188132 KB Output is correct
8 Correct 1054 ms 195788 KB Output is correct
9 Correct 898 ms 190828 KB Output is correct
10 Correct 810 ms 187748 KB Output is correct
11 Correct 832 ms 188388 KB Output is correct
12 Correct 907 ms 187748 KB Output is correct
13 Correct 1163 ms 195964 KB Output is correct
14 Correct 1197 ms 196140 KB Output is correct
15 Correct 1204 ms 195992 KB Output is correct
16 Correct 1198 ms 195776 KB Output is correct
17 Correct 1042 ms 188140 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 124908 KB Output is correct
2 Correct 272 ms 124908 KB Output is correct
3 Correct 265 ms 124908 KB Output is correct
4 Correct 275 ms 124908 KB Output is correct
5 Correct 261 ms 125036 KB Output is correct
6 Correct 261 ms 124908 KB Output is correct
7 Correct 258 ms 125036 KB Output is correct
8 Correct 265 ms 124952 KB Output is correct
9 Correct 257 ms 124928 KB Output is correct
10 Correct 265 ms 126060 KB Output is correct
11 Correct 273 ms 126060 KB Output is correct
12 Correct 281 ms 125932 KB Output is correct
13 Correct 264 ms 126060 KB Output is correct
14 Correct 280 ms 126188 KB Output is correct
15 Correct 266 ms 126060 KB Output is correct
16 Correct 1117 ms 187160 KB Output is correct
17 Correct 1119 ms 195940 KB Output is correct
18 Correct 998 ms 190924 KB Output is correct
19 Correct 987 ms 188576 KB Output is correct
20 Correct 974 ms 188388 KB Output is correct
21 Correct 1058 ms 188132 KB Output is correct
22 Correct 1069 ms 188132 KB Output is correct
23 Correct 1054 ms 195788 KB Output is correct
24 Correct 898 ms 190828 KB Output is correct
25 Correct 810 ms 187748 KB Output is correct
26 Correct 832 ms 188388 KB Output is correct
27 Correct 907 ms 187748 KB Output is correct
28 Correct 1163 ms 195964 KB Output is correct
29 Correct 1197 ms 196140 KB Output is correct
30 Correct 1204 ms 195992 KB Output is correct
31 Correct 1198 ms 195776 KB Output is correct
32 Correct 1042 ms 188140 KB Output is correct
33 Correct 1196 ms 190036 KB Output is correct
34 Correct 680 ms 157924 KB Output is correct
35 Correct 1252 ms 195428 KB Output is correct
36 Correct 1153 ms 189156 KB Output is correct
37 Correct 1237 ms 193764 KB Output is correct
38 Correct 1188 ms 190396 KB Output is correct
39 Correct 1127 ms 203620 KB Output is correct
40 Correct 1254 ms 199560 KB Output is correct
41 Correct 1089 ms 192740 KB Output is correct
42 Correct 971 ms 189412 KB Output is correct
43 Correct 1260 ms 200276 KB Output is correct
44 Correct 1190 ms 193576 KB Output is correct
45 Correct 1022 ms 204004 KB Output is correct
46 Correct 1042 ms 203620 KB Output is correct
47 Correct 1167 ms 195940 KB Output is correct
48 Correct 1163 ms 195728 KB Output is correct
49 Correct 1174 ms 195900 KB Output is correct
50 Correct 1175 ms 195816 KB Output is correct
51 Correct 1194 ms 200164 KB Output is correct
52 Correct 1206 ms 199944 KB Output is correct