Submission #641528

#	Time	Username	Problem	Language	Result	Execution time	Memory
641528		ymm	Werewolf (IOI18_werewolf)	C++17	100 / 100	1286 ms	166556 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 18;
const int M = 400'010;

struct {
	int par[N];
	set<int> ppar[N];

	int rt(int v) {return par[v]==-1? v: (par[v] = rt(par[v]));}
	void unite(int v, int u)
	{
		u = rt(u);
		assert(v == rt(v));
		assert(v >= u);
		if (v == u)
			return;
		par[u] = v;
		assert(ppar[u].size() && *ppar[u].begin() == v);
		ppar[u].erase(ppar[u].begin());
		if (ppar[v].size() < ppar[u].size())
			ppar[v].swap(ppar[u]);
		for (int x : ppar[u]) {
			ppar[v].insert(x);
		}
		{ set<int> tmp; ppar[u].swap(tmp); }
	}

	void init()
	{
		Loop (i,0,N) {
			par[i] = -1;
			{ set<int> tmp; ppar[i].swap(tmp); }
		}
	}

	void up(int v, int x)
	{
		assert(v == rt(v));
		assert(x > v);
		ppar[v].insert(x);
	}
} dsul, dsur;

struct {
	vector<int> A[N];
	int par[N][lg];
	int l[N], r[N];

	void dfs(int v, int p, vector<int> &ord)
	{
		l[v] = ord.size();
		ord.push_back(v);
		par[v][0] = p;
		Loop (i,0,lg-1)
			par[v][i+1] = par[par[v][i]][i];
		for (int u : A[v])
			if (u != p)
				dfs(u, v, ord);
		r[v] = ord.size();
	}

	int get_anc(int v, int r)
	{
		LoopR (i,0,lg) {
			if (par[v][i] < r)
				v = par[v][i];
		}
		return v;
	}
} dfsl, dfsr;

namespace seg
{
	struct node {
		int l, r;
		int x;
	} nodes[256'000'000/sizeof(node)];
	int next = 1;

	int new_node(int l, int r)
	{
		nodes[next].l = l;
		nodes[next].r = r;
		nodes[next].x = nodes[l].x + nodes[r].x;
		return next++;
	}
	int new_node(int x)
	{
		nodes[next].l = nodes[next].r = 0;
		nodes[next].x = x;
		return next++;
	}

	int up(int t, int p, int b=0, int e=N)
	{
		if (e - b == 1)
			return new_node(nodes[t].x + 1);
		if (p < (b+e)/2)
			return new_node(up(nodes[t].l, p, b, (b+e)/2), nodes[t].r);
		else
			return new_node(nodes[t].l, up(nodes[t].r, p, (b+e)/2, e));
	}

	int get(int t1, int t2, int l, int r, int b=0, int e=N)
	{
		//cout << l << ' ' << r << " !" << endl;
		//cout << b << ' ' << e << " !" << endl;
		//cout << nodes[t2].x - nodes[t1].x << endl;
		if (l <= b && e <= r)
			return nodes[t2].x - nodes[t1].x;
		if (r <= b || e <= l)
			return 0;
		return   get(nodes[t1].l,nodes[t2].l,l,r,b,(b+e)/2)
		       + get(nodes[t1].r,nodes[t2].r,l,r,(b+e)/2,e);
	}

	int init(int b=0, int e=N)
	{
		if (e-b == 1)
			return new_node(1);
		return new_node(init(b,(b+e)/2),init((b+e)/2,e));
	}

	int rt[N];
}

vector<int> A[N];

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)
{
	int m = x.size();
	Loop (i,0,m) {
		A[x[i]].push_back(y[i]);
		A[y[i]].push_back(x[i]);
	}

	dsur.init();
	Loop (v,0,n) {
		for (int u : A[v]) {
			if (u < v)
				dsur.unite(v, u);
		}
		for (int u : A[v]) {
			if (u > v)
				dsur.up(v, u);
		}
		assert(v == n-1 || dsur.ppar[v].size());
		if (dsur.ppar[v].size()) {
			dfsr.A[*dsur.ppar[v].begin()].push_back(v);
		}
	}
	dsul.init();
	LoopR (v,0,n) {
		for (int u : A[v]) {
			if (u > v)
				dsul.unite(n - v, n - u);
		}
		for (int u : A[v]) {
			if (u < v)
				dsul.up(n - v, n - u);
		}
		assert(v == 0 || dsul.ppar[n - v].size());
		if (dsul.ppar[n - v].size()) {
			dfsl.A[*dsul.ppar[n - v].begin()].push_back(n - v);
		}
	}

	vector<int> v1, v2, v3(n);
	dfsr.dfs(n-1, n-1, v1);
	dfsl.dfs(n, n, v2);
	//cout << "hi" << endl;
	for (int &x : v2) x = n-x;
	//Loop (i,0,n) cout << v1[i] << ' '; cout << endl;
	//Loop (i,0,n) cout << v2[i] << ' '; cout << endl;
	assert(v1.size() == n);
	assert(v2.size() == n);
	Loop (i,0,n) v3[v1[i]] = i;
	Loop (i,0,n) v2[i] = v3[v2[i]];
	//Loop (i,0,n) cout << v2[i] << ' '; cout << endl;
	//cout << "hi" << endl;

	seg::rt[0] = seg::init();
	//cout << "hi" << endl;
	Loop (i,0,n)
		seg::rt[i+1] = seg::up(seg::rt[i], v2[i]);
	
	//cout << "hi" << endl;
	vector<int> ans(s.size());
	Loop (i,0,s.size()) {
		//cout << l[i] << ' ' << r[i] << endl;
		//cout << s[i] << ' ' << e[i] << endl;
		e[i] = dfsr.get_anc(e[i], r[i]+1);
		s[i] = dfsl.get_anc(n-s[i], n-l[i]+1);
		//cout << n-s[i] << ' ' << e[i] << endl;
		int t1 = dfsl.l[s[i]];
		int t2 = dfsl.r[s[i]];
		int l = dfsr.l[e[i]];
		int r = dfsr.r[e[i]];
		//cout << t1 << ' ' << t2 << endl;
		//cout << l << ' ' << r << endl;
		ans[i] = !!seg::get(seg::rt[t1], seg::rt[t2], l, r);
		//cout << "--" << endl;
	}
	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:2:
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:186:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  186 |  assert(v1.size() == n);
      |         ~~~~~~~~~~^~~~
werewolf.cpp:187:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  187 |  assert(v2.size() == n);
      |         ~~~~~~~~~~^~~~
werewolf.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
werewolf.cpp:200:2: note: in expansion of macro 'Loop'
  200 |  Loop (i,0,s.size()) {
      |  ^~~~

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