Submission #382296

#	Time	Username	Problem	Language	Result	Execution time	Memory
382296		luciocf	늑대인간 (IOI18_werewolf)	C++14	15 / 100	186 ms	31340 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int maxn = 6e4+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 SegmentTree
{
	int tree[4*maxn];

	void upd(int node, int l, int r, int pos, int v)
	{
		if (l == r)
		{
			tree[node] = max(tree[node], v);
			return;
		}

		int mid = (l+r)>>1;

		if (pos <= mid) upd(2*node, l, mid, pos, v);
		else upd(2*node+1, mid+1, r, pos, v);

		tree[node] = max(tree[2*node], tree[2*node+1]);
	}

	int query(int node, int l, int r, int a, int b)
	{
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];

		int mid = (l+r)>>1;

		return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
	}
} seg;

struct Event
{
	int x1, x2, y1, y2, t, ind;

	bool operator <(const Event &o)
	{
		if (o.x2 == x2) return t < o.t;
		return x2 < o.x2;
	}
} 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) seg.upd(1, 1, maxn-1, E.y1, E.x1);
		else ans[E.ind] = (seg.query(1, 1, maxn-1, E.y1, E.y2) >= E.x1 ? 1 : 0);
	}
}

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], en[0][u], st[1][v], en[1][v], 1, i+1};
	}

	for (int i = 1; i <= n; i++)
		event[++queries] = {st[0][i], 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]);

	return final;
}

Compilation message (stderr)

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:181:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |  for (int i = 0; i < X.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:195:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |  for (int i = 0; i < S.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:212:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |  for (int i = 1; i <= S.size(); i++)
      |                  ~~^~~~~~~~~~~

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