oj.uz

Submission #1029744

# Submission time Handle Problem Language Result Execution time Memory
1029744 2024-07-21T08:51:37 Z AmirAli_H1 Werewolf (IOI18_werewolf) C++17
100 / 100
 619 ms 218296 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int maxs = 4 * maxn;
const int oo = 1e9 + 7;

int n, m, q;
vector<int> adj[maxn], adjx[maxs];
int val1, val2, sz, p[maxs], A[maxs];
vector<pii> Q1[maxs], Q2[maxs];
int R1[maxn], R2[maxn]; set<int> gooni[maxs];
int st[maxs], ft[maxs], timer = 0;
vector<pair<pii, int>> Q[maxs];
vector<pii> G1, G2; vector<int> res;

int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}

void merge(int a, int b, int x) {
	a = get(a); b = get(b);
	if (a == b) return ;
	int v = sz++; A[v] = x;
	p[v] = v; p[a] = v; p[b] = v;
	adjx[v].pb(a); adjx[v].pb(b);
}

void dfs(int v, bool time) {
	if (time) st[v] = timer++;
	G1.pb(Mp(A[v], v)); G2.pb(Mp(-A[v], v));
	
	for (auto f : Q1[v]) {
		int j = lower_bound(all(G1), Mp(f.F, -oo)) - G1.begin();
		R1[f.S] = G1[j].S;
	}
	for (auto f : Q2[v]) {
		int j = lower_bound(all(G2), Mp(-f.F, -oo)) - G2.begin();
		R2[f.S] = G2[j].S;
	}
	
	for (int u : adjx[v]) {
		dfs(u, time);
	}
	
	G1.pop_back(); G2.pop_back();
	if (time) ft[v] = timer;
}

void sack(int v) {
	if (len(adjx[v]) == 0) gooni[v].insert(st[v]);
	for (int u : adjx[v]) {
		sack(u);
		if (len(gooni[u]) > len(gooni[v])) swap(gooni[u], gooni[v]);
		for (int x : gooni[u]) gooni[v].insert(x);
		gooni[u].clear();
	}
	for (auto f : Q[v]) {
		int l = f.F.F, r = f.F.S, j = f.S;
		auto it = gooni[v].lower_bound(l);
		if (it != gooni[v].end() && (*it) < r) res[j] = 1;
		else res[j] = 0;
	}
}

vector<int> check_validity(int Nx, vector<int> ux, vector<int> vx,
								vector<int> sx, vector<int> ex,
								vector<int> lx, vector<int> rx) {
	n = Nx; m = len(ux); q = len(sx);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(v); adj[v].pb(u);
	}
	
	val1 = 0; sz = val1 + n;
	iota(p + val1, p + sz, val1);
	iota(A + val1, A + sz, 0);
	for (int i = n - 1; i >= 0; i--) {
		for (int j : adj[i]) {
			if (j > i) merge(i + val1, j + val1, i);
		}
	}
	int v1 = sz - 1;
	
	val2 = sz; sz = val2 + n;
	iota(p + val2, p + sz, val2);
	iota(A + val2, A + sz, 0);
	for (int i = 0; i < n; i++) {
		for (int j : adj[i]) {
			if (j < i) merge(i + val2, j + val2, i);
		}
	}
	int v2 = sz - 1;
	
	for (int i = 0; i < q; i++) {
		int s = sx[i], e = ex[i];
		int l = lx[i], r = rx[i];
		Q1[s + val1].pb(Mp(l, i));
		Q2[e + val2].pb(Mp(r, i));
	}
	
	dfs(v1, 1); dfs(v2, 0);
	for (int v = val2; v < val2 + n; v++) st[v] = st[v - val2];
	
	res.resize(q);
	for (int i = 0; i < q; i++) {
		int u1 = R1[i], u2 = R2[i];
		Q[u2].pb(Mp(Mp(st[u1], ft[u1]), i));
	}
	sack(v2);
	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 117772 KB Output is correct
2 Correct 47 ms 117844 KB Output is correct
3 Correct 45 ms 117852 KB Output is correct
4 Correct 47 ms 117848 KB Output is correct
5 Correct 47 ms 117708 KB Output is correct
6 Correct 50 ms 117844 KB Output is correct
7 Correct 52 ms 117836 KB Output is correct
8 Correct 47 ms 117844 KB Output is correct
9 Correct 46 ms 117732 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 117772 KB Output is correct
2 Correct 47 ms 117844 KB Output is correct
3 Correct 45 ms 117852 KB Output is correct
4 Correct 47 ms 117848 KB Output is correct
5 Correct 47 ms 117708 KB Output is correct
6 Correct 50 ms 117844 KB Output is correct
7 Correct 52 ms 117836 KB Output is correct
8 Correct 47 ms 117844 KB Output is correct
9 Correct 46 ms 117732 KB Output is correct
10 Correct 50 ms 118872 KB Output is correct
11 Correct 49 ms 118876 KB Output is correct
12 Correct 55 ms 118616 KB Output is correct
13 Correct 51 ms 119124 KB Output is correct
14 Correct 50 ms 119124 KB Output is correct
15 Correct 51 ms 118864 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 184036 KB Output is correct
2 Correct 432 ms 194924 KB Output is correct
3 Correct 447 ms 185764 KB Output is correct
4 Correct 457 ms 190128 KB Output is correct
5 Correct 480 ms 190036 KB Output is correct
6 Correct 519 ms 190292 KB Output is correct
7 Correct 603 ms 191624 KB Output is correct
8 Correct 404 ms 199700 KB Output is correct
9 Correct 422 ms 189392 KB Output is correct
10 Correct 405 ms 185648 KB Output is correct
11 Correct 414 ms 185432 KB Output is correct
12 Correct 439 ms 184856 KB Output is correct
13 Correct 483 ms 207724 KB Output is correct
14 Correct 472 ms 207664 KB Output is correct
15 Correct 475 ms 207724 KB Output is correct
16 Correct 517 ms 207736 KB Output is correct
17 Correct 562 ms 191240 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 117772 KB Output is correct
2 Correct 47 ms 117844 KB Output is correct
3 Correct 45 ms 117852 KB Output is correct
4 Correct 47 ms 117848 KB Output is correct
5 Correct 47 ms 117708 KB Output is correct
6 Correct 50 ms 117844 KB Output is correct
7 Correct 52 ms 117836 KB Output is correct
8 Correct 47 ms 117844 KB Output is correct
9 Correct 46 ms 117732 KB Output is correct
10 Correct 50 ms 118872 KB Output is correct
11 Correct 49 ms 118876 KB Output is correct
12 Correct 55 ms 118616 KB Output is correct
13 Correct 51 ms 119124 KB Output is correct
14 Correct 50 ms 119124 KB Output is correct
15 Correct 51 ms 118864 KB Output is correct
16 Correct 614 ms 184036 KB Output is correct
17 Correct 432 ms 194924 KB Output is correct
18 Correct 447 ms 185764 KB Output is correct
19 Correct 457 ms 190128 KB Output is correct
20 Correct 480 ms 190036 KB Output is correct
21 Correct 519 ms 190292 KB Output is correct
22 Correct 603 ms 191624 KB Output is correct
23 Correct 404 ms 199700 KB Output is correct
24 Correct 422 ms 189392 KB Output is correct
25 Correct 405 ms 185648 KB Output is correct
26 Correct 414 ms 185432 KB Output is correct
27 Correct 439 ms 184856 KB Output is correct
28 Correct 483 ms 207724 KB Output is correct
29 Correct 472 ms 207664 KB Output is correct
30 Correct 475 ms 207724 KB Output is correct
31 Correct 517 ms 207736 KB Output is correct
32 Correct 562 ms 191240 KB Output is correct
33 Correct 619 ms 193488 KB Output is correct
34 Correct 225 ms 160008 KB Output is correct
35 Correct 576 ms 202096 KB Output is correct
36 Correct 571 ms 191792 KB Output is correct
37 Correct 616 ms 200128 KB Output is correct
38 Correct 576 ms 193656 KB Output is correct
39 Correct 564 ms 218296 KB Output is correct
40 Correct 548 ms 205948 KB Output is correct
41 Correct 487 ms 193348 KB Output is correct
42 Correct 445 ms 185992 KB Output is correct
43 Correct 536 ms 203104 KB Output is correct
44 Correct 520 ms 195264 KB Output is correct
45 Correct 448 ms 213432 KB Output is correct
46 Correct 466 ms 213296 KB Output is correct
47 Correct 478 ms 207984 KB Output is correct
48 Correct 477 ms 207600 KB Output is correct
49 Correct 454 ms 207764 KB Output is correct
50 Correct 479 ms 207816 KB Output is correct
51 Correct 578 ms 207964 KB Output is correct
52 Correct 589 ms 208500 KB Output is correct