Submission #1301638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301638		TIN	Werewolf (IOI18_werewolf)	C++17	Compilation error	0 ms	0 KiB

werewolf

#include "werewolf.h"

#include <algorithm>
#include <functional>

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R)
{
// construct graph
	std::vector<std::vector<int>> adj(N + 1);
	int M = X.size();
	for (int i = 0; i < M; ++i)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
// Construct KRTs
	std::vector<int> par(N + 1);
	std::vector<int> sz(N + 1);
	std::function<int(int)> find_set;
	find_set = [&](int v) -> int
	{
		if (v == par[v]) return v;
		return par[v] = find_set(par[v]);
	};
	int dfsTimer;
	// construct KRT for left threshold
	std::iota(par.begin(), par.end(), 0);
	std::fill(sz.begin(), sz.end(), 0);
	std::vector<std::vector<int>> tree1(N + 1);
	for (int i = N; i >= 1; --i)
	{
		sz[i] = 1;
		for (int j : adj[i]) if (sz[j])
		{
			int p = find_set(j);
			tree1[i].push_back(p);
		}
		for (int j : adj[i]) if (sz[j])
		{
			int p = find_set(j);
			par[p] = i;
			sz[i] += sz[p];
		}
	}
	dfsTimer = 0;
	std::vector<int> tin1(N + 1), tout1(N + 1), A(N + 1);
	std::vector<int> posA(N + 1);
	function<void(int)> DFS1;
	DFS1 = [&](int u)
	{
		tin1[u] = ++dfsTimer;
		A[tin1[u]] = u;
		posA[u] = tin1[u];
		for (int v : tree1[u]) DFS1(v);
		tout1[u] = dfsTimer;
	};
	DFS1(1);
	// construct KRT for right threshold
	std::iota(par.begin(), par.end(), 0);
	std::fill(sz.begin(), sz.end(), 0);
	std::vector<std::vector<int>> tree2(N + 1);
	for (int i = 1; i <= N; ++i)
	{
		sz[i] = 1;
		for (int j : adj[i]) if (sz[j])
		{
			int p = find_set(j);
			tree2[i].push_back(p);
		}
		for (int j : adj[i]) if (sz[j])
		{
			int p = find_set(j);
			par[p] = i;
			sz[i] += sz[p];
		}
	}
	dfsTimer = 0;
	std::vector<int> tin2(N + 1), tout2(N + 1), B(N + 1);
	function<void(int)> DFS1;
	DFS2 = [&](int u)
	{
		tin2[u] = ++dfsTimer;
		B[tin2[u]] = u;
		for (int v : tree2[u]) DFS1(v);
		tout2[u] = dfsTimer;
	};
	DFS2(N);
// Sweep line to find answer
	int Q = S.size();
	std::vector<std::pair<int,int>> queries(Q);
	for (int i = 0; i < Q; ++i) queries[i] = {S[i], E[i]};
	std::vector<int> BIT(N + 1, 0);
	auto update = [&](int pos) -> int { for (; pos <= N; pos += pos & (-pos)) BIT[pos]++; };
	auto sum = [&](int pos) -> int { int ret = 0; for (; pos > 0; pos -= pos & (-pos)) ret += BIT[pos]; return ret; };
	auto query = [&](int l, int r) -> int {
		if (l > r) return 0;
		return sum(r) - sum(l - 1);
	};
	std::vector<std::vector<int>> queL(N + 1);
	for (int i = 0; i < Q; ++i) queL[tin2[E[i]] - 1].push_back(i);
	std::vector<std::vector<int>> queR(N + 1);
	for (int i = 0; i < Q; ++i) queR[tout2[E[i]]].push_back(i);
	std::vector<int> answer(Q, 0);
	for (int i = 1; i <= N; ++i)
	{
		update(posA[B[i]]);
		for (int qID : queL[i])
		{
			int u =	queries[qID].first;
			ans[qID] -= query(tin1[u], tout1[u]);
		}
		for (int qID : queR[i])
		{
			int u = queries[qID].first;
			ans[qID] += query(tin1[u], tout1[u]);
		}
	}
	return answer;
}

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:29:14: error: 'iota' is not a member of 'std'
   29 |         std::iota(par.begin(), par.end(), 0);
      |              ^~~~
werewolf.cpp:50:9: error: 'function' was not declared in this scope; did you mean 'std::function'?
   50 |         function<void(int)> DFS1;
      |         ^~~~~~~~
      |         std::function
In file included from /usr/include/c++/13/functional:59,
                 from werewolf.cpp:4:
/usr/include/c++/13/bits/std_function.h:111:11: note: 'std::function' declared here
  111 |     class function;
      |           ^~~~~~~~
werewolf.cpp:50:18: error: expected primary-expression before 'void'
   50 |         function<void(int)> DFS1;
      |                  ^~~~
werewolf.cpp:51:9: error: 'DFS1' was not declared in this scope
   51 |         DFS1 = [&](int u)
      |         ^~~~
werewolf.cpp:61:14: error: 'iota' is not a member of 'std'
   61 |         std::iota(par.begin(), par.end(), 0);
      |              ^~~~
werewolf.cpp:81:18: error: expected primary-expression before 'void'
   81 |         function<void(int)> DFS1;
      |                  ^~~~
werewolf.cpp:82:9: error: 'DFS2' was not declared in this scope
   82 |         DFS2 = [&](int u)
      |         ^~~~
werewolf.cpp: In lambda function:
werewolf.cpp:95:95: warning: no return statement in function returning non-void [-Wreturn-type]
   95 |         auto update = [&](int pos) -> int { for (; pos <= N; pos += pos & (-pos)) BIT[pos]++; };
      |                                                                                               ^
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:112:25: error: 'ans' was not declared in this scope; did you mean 'abs'?
  112 |                         ans[qID] -= query(tin1[u], tout1[u]);
      |                         ^~~
      |                         abs
werewolf.cpp:117:25: error: 'ans' was not declared in this scope; did you mean 'abs'?
  117 |                         ans[qID] += query(tin1[u], tout1[u]);
      |                         ^~~
      |                         abs