제출 #382302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382302		luciocf	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1260 ms	204004 KiB

werewolf

#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;
}

컴파일 시 표준 에러 (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: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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51