oj.uz

Submission #896642

# Submission time Handle Problem Language Result Execution time Memory
896642 2024-01-01T20:02:26 Z aykhn Werewolf (IOI18_werewolf) C++17
100 / 100
 977 ms 339840 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

struct SegTree
{
	int sz = 1;
	vector<int> st;
	void init(int n)
	{
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, 0);
	}
	void add(int l, int r, int x, int ind)
	{
		if (l + 1 == r) 
		{
			st[x]++;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) add(l, mid, 2*x + 1, ind);
		else add(mid, r, 2*x + 2, ind);
		st[x] = st[2*x + 1] + st[2*x + 2];
	}
	int get(int l, int r, int x, int lx, int rx)
	{
		if (l >= rx || r <= lx) return 0;
		if (l >= lx && r <= rx) return st[x];
		int mid = (l + r) >> 1;
		return get(l, mid, 2*x + 1, lx, rx) + get(mid, r, 2*x + 2, lx, rx);
	}
};

const int MXN = 1e6 + 6;
const int LOG = 20;

int nh, nw;
vector<int> hum[MXN], wol[MXN];
int eh[MXN], ew[MXN];
int ph[LOG][MXN], pw[LOG][MXN];
int whenh[MXN], whenw[MXN];
array<int, 2> rh[MXN], rw[MXN];
int idh[MXN], idw[MXN], revh[MXN], revw[MXN];
int tim;
int ans[MXN];
vector<array<int, 3>> qin[MXN], qout[MXN];
SegTree st;

void reset()
{
	for (int i = 0; i < MXN; i++) 
	{
		eh[i] = ew[i] = -1;
		rh[i][0] = rw[i][0] = inf;
		rh[i][1] = rw[i][1] = -inf;
		wol[i].clear();
		hum[i].clear();
	}
}
int geth(int x)
{
	if (eh[x] < 0) return x;
	return eh[x] = geth(eh[x]);
}
void uniteh(int x, int y)
{
	int val = x;
	x = geth(x);
	y = geth(y);
	if (x == y) return;
	whenh[nh] = val;
	hum[nh].pb(x);
	hum[nh].pb(y);
	eh[nh] = eh[x] + eh[y];
	eh[x] = eh[y] = nh;
	nh++;
}
void dfsh(int a)
{
	if (hum[a].empty())
	{
		idh[a] = ++tim;
		revh[tim] = a;
		rh[a][0] = rh[a][1] = idh[a];
		return;
	}
	for (int v : hum[a])
	{
		ph[0][v] = a;
		dfsh(v);
		rh[a][0] = min(rh[a][0], rh[v][0]);
		rh[a][1] = max(rh[a][1], rh[v][1]);
	}
}
int getw(int x)
{
	if (ew[x] < 0) return x;
	return ew[x] = getw(ew[x]);
}
void unitew(int x, int y)
{
	int val = y;
	x = getw(x);
	y = getw(y);
	if (x == y) return;
	whenw[nw] = val;
	wol[nw].pb(x);
	wol[nw].pb(y);
	ew[nw] = ew[x] + ew[y];
	ew[x] = ew[y] = nw;
	nw++;
}
void dfsw(int a)
{
	if (wol[a].empty())
	{
		idw[a] = ++tim;
		revw[tim] = a;
		rw[a][0] = rw[a][1] = idw[a];
		return;
	}
	for (int v : wol[a])
	{
		pw[0][v] = a;
		dfsw(v);
		rw[a][0] = min(rw[a][0], rw[v][0]);
		rw[a][1] = max(rw[a][1], rw[v][1]);
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) 
{
	reset();
	nh = nw = N;
	vector<array<int, 2>> edges;
	for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
	sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
	{
		return a[0] > b[0];
	});
	for (const array<int, 2> a : edges) uniteh(a[0], a[1]);
	sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
	{
		return a[1] < b[1];
	});
	for (const array<int, 2> a : edges) unitew(a[0], a[1]);
	tim = -1;
	ph[0][nh - 1] = nh - 1;
	dfsh(nh - 1);
	tim = -1;
	pw[0][nw - 1] = nw - 1;
	dfsw(nw - 1);
	for (int i = 1; i < LOG; i++) for (int j = 0; j < nh; j++) ph[i][j] = ph[i - 1][ph[i - 1][j]], pw[i][j] = pw[i - 1][pw[i - 1][j]];
	int Q = S.size();
	for (int i = 0; i < Q; i++)
	{
		int u = S[i], v = E[i], l = L[i], r = R[i];
		for (int j = LOG - 1; j >= 0; j--)
		{
			if (whenh[ph[j][u]] >= l) u = ph[j][u];
			if (whenw[pw[j][v]] <= r) v = pw[j][v];
		}
		qin[rh[u][0]].pb({rw[v][0], rw[v][1], i});
		qout[rh[u][1]].pb({rw[v][0], rw[v][1], i});
	}
	st.init(nw);
	for (int i = 0; i < nh; i++)
	{
		for (const array<int, 3> a : qin[i]) ans[a[2]] = st.get(0, st.sz, 0, a[0], a[1] + 1);
		st.add(0, st.sz, 0, idw[revh[i]]);
		for (const array<int, 3> a : qout[i]) ans[a[2]] = (st.get(0, st.sz, 0, a[0], a[1] + 1) > ans[a[2]] ? 1 : 0);
	}
	vector<int> res;
	for (int i = 0; i < Q; i++) res.pb(ans[i]);
	return res;
}

Compilation message

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:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
      |                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 211292 KB Output is correct
2 Correct 35 ms 211292 KB Output is correct
3 Correct 36 ms 211668 KB Output is correct
4 Correct 35 ms 211288 KB Output is correct
5 Correct 35 ms 211280 KB Output is correct
6 Correct 34 ms 211316 KB Output is correct
7 Correct 35 ms 211284 KB Output is correct
8 Correct 34 ms 211336 KB Output is correct
9 Correct 35 ms 211396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 211292 KB Output is correct
2 Correct 35 ms 211292 KB Output is correct
3 Correct 36 ms 211668 KB Output is correct
4 Correct 35 ms 211288 KB Output is correct
5 Correct 35 ms 211280 KB Output is correct
6 Correct 34 ms 211316 KB Output is correct
7 Correct 35 ms 211284 KB Output is correct
8 Correct 34 ms 211336 KB Output is correct
9 Correct 35 ms 211396 KB Output is correct
10 Correct 40 ms 212076 KB Output is correct
11 Correct 42 ms 212048 KB Output is correct
12 Correct 39 ms 212052 KB Output is correct
13 Correct 40 ms 212304 KB Output is correct
14 Correct 40 ms 212560 KB Output is correct
15 Correct 41 ms 212104 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 318588 KB Output is correct
2 Correct 740 ms 332312 KB Output is correct
3 Correct 667 ms 328128 KB Output is correct
4 Correct 697 ms 325568 KB Output is correct
5 Correct 768 ms 325828 KB Output is correct
6 Correct 830 ms 326852 KB Output is correct
7 Correct 710 ms 325312 KB Output is correct
8 Correct 598 ms 332436 KB Output is correct
9 Correct 412 ms 327328 KB Output is correct
10 Correct 340 ms 325412 KB Output is correct
11 Correct 387 ms 325200 KB Output is correct
12 Correct 378 ms 324896 KB Output is correct
13 Correct 742 ms 331688 KB Output is correct
14 Correct 692 ms 331712 KB Output is correct
15 Correct 714 ms 331852 KB Output is correct
16 Correct 724 ms 331800 KB Output is correct
17 Correct 699 ms 325568 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 211292 KB Output is correct
2 Correct 35 ms 211292 KB Output is correct
3 Correct 36 ms 211668 KB Output is correct
4 Correct 35 ms 211288 KB Output is correct
5 Correct 35 ms 211280 KB Output is correct
6 Correct 34 ms 211316 KB Output is correct
7 Correct 35 ms 211284 KB Output is correct
8 Correct 34 ms 211336 KB Output is correct
9 Correct 35 ms 211396 KB Output is correct
10 Correct 40 ms 212076 KB Output is correct
11 Correct 42 ms 212048 KB Output is correct
12 Correct 39 ms 212052 KB Output is correct
13 Correct 40 ms 212304 KB Output is correct
14 Correct 40 ms 212560 KB Output is correct
15 Correct 41 ms 212104 KB Output is correct
16 Correct 943 ms 318588 KB Output is correct
17 Correct 740 ms 332312 KB Output is correct
18 Correct 667 ms 328128 KB Output is correct
19 Correct 697 ms 325568 KB Output is correct
20 Correct 768 ms 325828 KB Output is correct
21 Correct 830 ms 326852 KB Output is correct
22 Correct 710 ms 325312 KB Output is correct
23 Correct 598 ms 332436 KB Output is correct
24 Correct 412 ms 327328 KB Output is correct
25 Correct 340 ms 325412 KB Output is correct
26 Correct 387 ms 325200 KB Output is correct
27 Correct 378 ms 324896 KB Output is correct
28 Correct 742 ms 331688 KB Output is correct
29 Correct 692 ms 331712 KB Output is correct
30 Correct 714 ms 331852 KB Output is correct
31 Correct 724 ms 331800 KB Output is correct
32 Correct 699 ms 325568 KB Output is correct
33 Correct 924 ms 328648 KB Output is correct
34 Correct 277 ms 248760 KB Output is correct
35 Correct 945 ms 332744 KB Output is correct
36 Correct 952 ms 328020 KB Output is correct
37 Correct 977 ms 331652 KB Output is correct
38 Correct 950 ms 329104 KB Output is correct
39 Correct 884 ms 339840 KB Output is correct
40 Correct 638 ms 336104 KB Output is correct
41 Correct 488 ms 329408 KB Output is correct
42 Correct 391 ms 325728 KB Output is correct
43 Correct 649 ms 338276 KB Output is correct
44 Correct 570 ms 330948 KB Output is correct
45 Correct 442 ms 338208 KB Output is correct
46 Correct 481 ms 338232 KB Output is correct
47 Correct 769 ms 332224 KB Output is correct
48 Correct 754 ms 331972 KB Output is correct
49 Correct 727 ms 332212 KB Output is correct
50 Correct 756 ms 331908 KB Output is correct
51 Correct 489 ms 336688 KB Output is correct
52 Correct 560 ms 336512 KB Output is correct