oj.uz

Submission #85439

# Submission time Handle Problem Language Result Execution time Memory
85439 2018-11-20T00:46:10 Z qkxwsm Werewolf (IOI18_werewolf) C++14
100 / 100
 1131 ms 268112 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
	int operator()(int x) const
	{
		x ^= (x >> 20) ^ (x >> 12);
		return x ^ (x >> 7) ^ (x >> 4);
	}
	int operator()(long long x) const
	{
		return x ^ (x >> 32);
	}
};

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
template<class T, class U>
T normalize(T x, U mod = 1000000007)
{
	return (((x % mod) + mod) % mod);
}
static long long randomizell(long long mod)
{
	return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
static int randomize(int mod)
{
	return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
#define SZ(x) ((int) (x.size()))

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 400013

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<pii, pii> ppp;

int N, Q, T;
vector<int> edge[MAXN];
ppp quer[MAXN];
ppp range[MAXN];
vi ans;
int parent[2][MAXN];
int ord[2][MAXN];
int ancestor[2][20][MAXN];
int st[2][MAXN], ft[2][MAXN];
int pos[MAXN], arr[MAXN];
vector<int> edge1[2][MAXN];

struct dsu
{
	int dsu[MAXN];
	bool flag;
	int get(int u)
	{
		return ((u == dsu[u]) ? u : dsu[u] = get(dsu[u]));
	}
	void merge(int u, int v)
	{
		u = get(u);
		v = get(v);
		if (flag)
		{
			if (u > v) swap(u, v);
		}
		else
		{
			if (u < v) swap(u, v);
		}
		dsu[u] = v;
		// cerr << u << " => " << v << endl;
		return;
	}
};
void dfs(bool flag, int u)
{
	st[flag][u] = T;
	ft[flag][u] = T;
	ord[flag][T] = u;
	T++;
	for (int v : edge1[flag][u])
	{
		if (v == parent[flag][u]) continue;
		dfs(flag, v);
		ft[flag][u] = ft[flag][v];
	}
}

int fen[MAXN];

void update(int idx, int v)
{
	for (int e = idx + 1; e <= N; e += e & (-e))
	{
		fen[e] += v;
	}
	return;
}
int query(int idx)
{
	int res = 0;
	for (int e = idx + 1; e > 0; e -= e & (-e))
	{
		res += fen[e];
	}
	return res;
}
vector<ppp> queries[MAXN];
dsu d[2];

vi check_validity(int n, vi X, vi Y, vi s, vi e, vi l, vi r)
{
	N = n;
	d[0].flag = true;
	for (int i = 0; i < N; i++)
	{
		d[0].dsu[i] = i;
		d[1].dsu[i] = i;
		parent[0][i] = N;
		parent[1][i] = N;
	}
	for (int i = 0; i < SZ(X); i++)
	{
		int u = X[i], v = Y[i];
		edge[u].PB(v);
		edge[v].PB(u);
	}
	Q = SZ(s);
	ans.resize(Q);
	for (int i = 0; i < Q; i++)
	{
		swap(s[i], e[i]);
		quer[i] = MP(MP(l[i], r[i]), MP(s[i], e[i]));
	}
	for (int i = 0; i < N; i++)
	{
		for (int u : edge[i])
		{
			if (u > i) continue;
			u = d[0].get(u);
			if (u == i) continue;
			parent[0][u] = i;
			d[0].merge(u, i);
		}
	}
	for (int i = N - 1; i >= 0; i--)
	{
		for (int u : edge[i])
		{
			if (u < i) continue;
			u = d[1].get(u);
			if (u == i) continue;
			parent[1][u] = i;
			d[1].merge(u, i);
		}
	}
	for (int flag = 0; flag < 2; flag++)
	{
		// cerr << "tree\n";
		for (int i = 0; i < N; i++)
		{
			if (parent[flag][i] != N)
			{
				edge1[flag][i].PB(parent[flag][i]);
				edge1[flag][parent[flag][i]].PB(i);
				// cerr << i << ' ' << parent[flag][i] << endl;
			}
		}
		for (int i = 0; i < N; i++)
		{
			if (parent[flag][i] == N)
			{
				dfs(flag, i);
			}
		}
		T = 0;
		for (int i = 0; i <= 19; i++)
		{
			ancestor[flag][i][N] = N;
		}
		for (int i = 0; i < N; i++)
		{
			ancestor[flag][0][i] = parent[flag][i];
		}
		for (int i = 1; i <= 19; i++)
		{
			for (int j = 0; j < N; j++)
			{
				ancestor[flag][i][j] = ancestor[flag][i - 1][ancestor[flag][i - 1][j]];
			}
		}
	}
	// for (int flag = 0; flag < 2; flag++)
	// {
	// 	for (int i = 0; i < N; i++)
	// 	{
	// 		cerr << ord[flag][i] << ' ';
	// 	}
	// 	cerr << endl;
	// }
	for (int i = 0; i < Q; i++)
	{
		//l, r, s, e
		if (quer[i].se.fi > quer[i].fi.se || quer[i].se.se < quer[i].fi.fi)
		{
			ans[i] = 0;
			continue;
		}
		//how far up can you go without exceeding r...
		int u = quer[i].se.fi;
		for (int j = 19; j >= 0; j--)
		{
			if (ancestor[0][j][u] > quer[i].fi.se || ancestor[0][j][u] == N) continue;
			u = ancestor[0][j][u];
		}
		// cerr << "starts at " << i << " goes to " << u << endl;
		range[i].fi = MP(st[0][u], ft[0][u]);
		u = quer[i].se.se;
		for (int j = 19; j >= 0; j--)
		{
			if (ancestor[1][j][u] < quer[i].fi.fi || ancestor[1][j][u] == N) continue;
			u = ancestor[1][j][u];
		}
		range[i].se = MP(st[1][u], ft[1][u]);
		// cerr << quer[i].fi.fi << ' ' << quer[i].fi.se << ' ' << quer[i].se.fi << ' ' << quer[i].se.se << " ->\n";
		// cerr << range[i].fi.fi << ' ' << range[i].fi.se << ' ' << range[i].se.fi << ' ' << range[i].se.se << endl;
	}
	//GIVEN TWO SUBARRAYS OF BIG ARRAY, CHECK IF THEY HAVE ANY COMMON ELEMENTS!
	for (int i = 0; i < N; i++)
	{
		pos[ord[1][i]] = i;
	}
	for (int i = 0; i < N; i++)
	{
		arr[i] = pos[ord[0][i]];
		// debug(arr[i]);
	}
	for (int i = 0; i < Q; i++)
	{
		if (range[i].fi.fi != 0)
		{
			queries[range[i].fi.fi - 1].PB(MP(MP(i, -1), range[i].se));
		}
		queries[range[i].fi.se].PB(MP(MP(i, 1), range[i].se));
	}
	for (int i = 0; i < N; i++)
	{
		update(arr[i], 1);
		for (ppp p : queries[i])
		{
			// cerr << "idx " << p.fi.fi << " mult " << p.fi.se << " l " << p.se.fi - 1 << " r " << p.se.se << endl;
			ans[p.fi.fi] += (p.fi.se) * (query(p.se.se) - query(p.se.fi - 1));
		}
	}
	for (int i = 0; i < Q; i++)
	{
		ans[i] = (bool) ans[i];
	}
	return ans;
	//idx, plusminus, l, r
	//# of values between
	//is there any value inside L1...R1 in arr[L0...R0]?
	//now it's just: in this subrange of an array, is there a value between L and R?
	//(0...R) -> (L...N-1) with (S[i], E[i])
	//u know that S[i] can go anywhere in its tree as long as path doesn't contain #s >= R+1
	//and then you can unfold the tree!
	//oh each of them is like a tree, and each time you increase R you merge some trees together
	return ans;
}

Compilation message

werewolf.cpp:44:12: warning: 'int randomize(int)' defined but not used [-Wunused-function]
 static int randomize(int mod)
            ^~~~~~~~~
werewolf.cpp:40:18: warning: 'long long int randomizell(long long int)' defined but not used [-Wunused-function]
 static long long randomizell(long long mod)
                  ^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38392 KB Output is correct
2 Correct 39 ms 38508 KB Output is correct
3 Correct 36 ms 38508 KB Output is correct
4 Correct 36 ms 38508 KB Output is correct
5 Correct 36 ms 38576 KB Output is correct
6 Correct 36 ms 38576 KB Output is correct
7 Correct 43 ms 38604 KB Output is correct
8 Correct 40 ms 38604 KB Output is correct
9 Correct 37 ms 38640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38392 KB Output is correct
2 Correct 39 ms 38508 KB Output is correct
3 Correct 36 ms 38508 KB Output is correct
4 Correct 36 ms 38508 KB Output is correct
5 Correct 36 ms 38576 KB Output is correct
6 Correct 36 ms 38576 KB Output is correct
7 Correct 43 ms 38604 KB Output is correct
8 Correct 40 ms 38604 KB Output is correct
9 Correct 37 ms 38640 KB Output is correct
10 Correct 45 ms 40080 KB Output is correct
11 Correct 46 ms 40188 KB Output is correct
12 Correct 45 ms 40284 KB Output is correct
13 Correct 51 ms 40652 KB Output is correct
14 Correct 45 ms 40696 KB Output is correct
15 Correct 46 ms 40756 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1086 ms 126704 KB Output is correct
2 Correct 959 ms 140528 KB Output is correct
3 Correct 970 ms 145080 KB Output is correct
4 Correct 988 ms 151604 KB Output is correct
5 Correct 1030 ms 155636 KB Output is correct
6 Correct 1047 ms 155732 KB Output is correct
7 Correct 994 ms 160364 KB Output is correct
8 Correct 752 ms 176824 KB Output is correct
9 Correct 589 ms 177420 KB Output is correct
10 Correct 552 ms 177420 KB Output is correct
11 Correct 658 ms 177420 KB Output is correct
12 Correct 644 ms 177420 KB Output is correct
13 Correct 985 ms 182196 KB Output is correct
14 Correct 1016 ms 182208 KB Output is correct
15 Correct 1020 ms 182288 KB Output is correct
16 Correct 1042 ms 182336 KB Output is correct
17 Correct 1127 ms 182336 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38392 KB Output is correct
2 Correct 39 ms 38508 KB Output is correct
3 Correct 36 ms 38508 KB Output is correct
4 Correct 36 ms 38508 KB Output is correct
5 Correct 36 ms 38576 KB Output is correct
6 Correct 36 ms 38576 KB Output is correct
7 Correct 43 ms 38604 KB Output is correct
8 Correct 40 ms 38604 KB Output is correct
9 Correct 37 ms 38640 KB Output is correct
10 Correct 45 ms 40080 KB Output is correct
11 Correct 46 ms 40188 KB Output is correct
12 Correct 45 ms 40284 KB Output is correct
13 Correct 51 ms 40652 KB Output is correct
14 Correct 45 ms 40696 KB Output is correct
15 Correct 46 ms 40756 KB Output is correct
16 Correct 1086 ms 126704 KB Output is correct
17 Correct 959 ms 140528 KB Output is correct
18 Correct 970 ms 145080 KB Output is correct
19 Correct 988 ms 151604 KB Output is correct
20 Correct 1030 ms 155636 KB Output is correct
21 Correct 1047 ms 155732 KB Output is correct
22 Correct 994 ms 160364 KB Output is correct
23 Correct 752 ms 176824 KB Output is correct
24 Correct 589 ms 177420 KB Output is correct
25 Correct 552 ms 177420 KB Output is correct
26 Correct 658 ms 177420 KB Output is correct
27 Correct 644 ms 177420 KB Output is correct
28 Correct 985 ms 182196 KB Output is correct
29 Correct 1016 ms 182208 KB Output is correct
30 Correct 1020 ms 182288 KB Output is correct
31 Correct 1042 ms 182336 KB Output is correct
32 Correct 1127 ms 182336 KB Output is correct
33 Correct 1049 ms 182336 KB Output is correct
34 Correct 426 ms 182336 KB Output is correct
35 Correct 1131 ms 182336 KB Output is correct
36 Correct 990 ms 182336 KB Output is correct
37 Correct 1077 ms 187884 KB Output is correct
38 Correct 972 ms 194116 KB Output is correct
39 Correct 1022 ms 215608 KB Output is correct
40 Correct 1004 ms 217968 KB Output is correct
41 Correct 746 ms 222512 KB Output is correct
42 Correct 601 ms 228436 KB Output is correct
43 Correct 988 ms 241772 KB Output is correct
44 Correct 802 ms 241772 KB Output is correct
45 Correct 699 ms 257384 KB Output is correct
46 Correct 764 ms 257384 KB Output is correct
47 Correct 902 ms 257384 KB Output is correct
48 Correct 927 ms 257384 KB Output is correct
49 Correct 899 ms 257384 KB Output is correct
50 Correct 974 ms 257384 KB Output is correct
51 Correct 957 ms 267968 KB Output is correct
52 Correct 908 ms 268112 KB Output is correct