oj.uz

Submission #990172

# Submission time Handle Problem Language Result Execution time Memory
990172 2024-05-29T17:56:35 Z vqpahmad Werewolf (IOI18_werewolf) C++17
100 / 100
 764 ms 305336 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct MergeTree {
	int p[MAXN], s[MAXN], lebal[MAXN];
	int cur_node;
	vector<int> adj[MAXN];
	void init(int n){
		cur_node = n;
		for (int i = 0; i < n; i++){
			p[i] = i;
			s[i] = 1;
			lebal[i] = i;
		}
	}
	int find(int u){
		if (p[u] == u) return u;
		return p[u] = find(p[u]);
	}
	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if (u == v) return;
		adj[cur_node].pb(lebal[u]);
		adj[cur_node].pb(lebal[v]);
		adj[lebal[u]].pb(cur_node);
		adj[lebal[v]].pb(cur_node);

		if (s[u] < s[v]) swap(u, v);
		s[u] += s[v];
		p[v] = u;
		lebal[u] = cur_node++;
	}
	int st[MAXN], ft[MAXN], timer = 1;
	int mn[MAXN], mx[MAXN]; // for humans I need min, for werewolf max
	int fa[MAXN][20];
	void dfs(int node, int par){
		st[node] = timer++;
		fa[node][0] = par;
		for (int b = 1; b < 20; b++){
			fa[node][b] = fa[fa[node][b - 1]][b - 1];
		}
		if (sz(adj[node]) == 1 && adj[node][0] == par){
			mx[node] = node;
			mn[node] = node;
		}
		for (auto to : adj[node]){
			if (to != par){
				dfs(to, node);
				ckmax(mx[node], mx[to]);
				ckmin(mn[node], mn[to]);
			}
		}
		ft[node] = timer++;
	}
	void get_dfs_order(){
		cur_node--;
		for (int i = 0; i <= cur_node; i++){
			mn[i] = inf;
			mx[i] = -inf;
		}
		dfs(cur_node, cur_node);
	}
	pii find_range(int u, int time, bool human){
		for (int b = 19; b >= 0; b--){
			if (human && mn[fa[u][b]] >= time){
				u = fa[u][b];
			}
			if (!human && mx[fa[u][b]] <= time){
				u = fa[u][b];
			}
		}
		return {st[u], ft[u]};
	}
	void dbg(){
		cout << "HERE\n";
		for (int i = 0; i <= cur_node; i++){
			cout << i << ' ' << st[i] << ' ' << ft[i] << ' ' << mn[i] << ' ' << mx[i] << endl;
		}
	}
} human, werewolf;

const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off<<1];
	void update(int idx, int u){
		t[idx+=off] += u;
		while (idx/=2)
			t[idx] = t[ls] + t[rs];
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return 0;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return get(l, r, ls, lo, mi)+get(l, r, rs, mi, hi);
	}
} seg;

vector<int> adj[MAXN];
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	int m = sz(X);
	int Q = S.size();
	for (int i = 0; i < m; i++){
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	werewolf.init(n);
	for (int i = 0; i < n; i++){
		// I want to caclute component for werewolf for L <= i
		for (auto u : adj[i]){
			if (u <= i){
				werewolf.merge(i, u);
			}
		}
	}
	human.init(n);
	for (int i = n - 1; i >= 0; i--){
		// I want to caclute component for werewolf for L <= i
		for (auto u : adj[i]){
			if (u >= i){
				human.merge(i, u);
			}
		}
	}
	werewolf.get_dfs_order();
	human.get_dfs_order();
	//werewolf.dbg();
	//human.dbg();
	vector<int> add[MAXN];
	for (int i = 0; i < n; i++){
		add[human.st[i]].pb(werewolf.st[i]);
	}
	vector<array<int, 4>> Queries[MAXN]; // type, bot, top, idx
	for (int i = 0; i < Q; i++){
		pii hr = human.find_range(S[i], L[i], 1);
		pii wr = werewolf.find_range(E[i], R[i], 0);
		Queries[hr.F - 1].pb({-1, wr.F, wr.S, i});
		Queries[hr.S].pb({1, wr.F, wr.S, i});
	}
	vector<int> ans(Q);
	for (int i = 0; i < MAXN; i++){
		for (auto pos : add[i]){
			seg.update(pos, 1);
		}
		for (auto [type, bot, top, idx] : Queries[i]){
			ans[idx] += type * seg.get(bot, top);
		}
	}
	for (int i = 0; i < Q; ++i) {
		ans[i] = !!ans[i];
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 150108 KB Output is correct
2 Correct 42 ms 150100 KB Output is correct
3 Correct 43 ms 150108 KB Output is correct
4 Correct 43 ms 150100 KB Output is correct
5 Correct 43 ms 150096 KB Output is correct
6 Correct 43 ms 150100 KB Output is correct
7 Correct 43 ms 150100 KB Output is correct
8 Correct 42 ms 150096 KB Output is correct
9 Correct 42 ms 150100 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 150108 KB Output is correct
2 Correct 42 ms 150100 KB Output is correct
3 Correct 43 ms 150108 KB Output is correct
4 Correct 43 ms 150100 KB Output is correct
5 Correct 43 ms 150096 KB Output is correct
6 Correct 43 ms 150100 KB Output is correct
7 Correct 43 ms 150100 KB Output is correct
8 Correct 42 ms 150096 KB Output is correct
9 Correct 42 ms 150100 KB Output is correct
10 Correct 49 ms 151124 KB Output is correct
11 Correct 51 ms 151092 KB Output is correct
12 Correct 61 ms 150964 KB Output is correct
13 Correct 49 ms 151124 KB Output is correct
14 Correct 49 ms 151008 KB Output is correct
15 Correct 49 ms 151120 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 289120 KB Output is correct
2 Correct 604 ms 300116 KB Output is correct
3 Correct 609 ms 297556 KB Output is correct
4 Correct 635 ms 295872 KB Output is correct
5 Correct 597 ms 295984 KB Output is correct
6 Correct 637 ms 297292 KB Output is correct
7 Correct 609 ms 295696 KB Output is correct
8 Correct 507 ms 299852 KB Output is correct
9 Correct 525 ms 295848 KB Output is correct
10 Correct 464 ms 295868 KB Output is correct
11 Correct 477 ms 295612 KB Output is correct
12 Correct 504 ms 295100 KB Output is correct
13 Correct 657 ms 299460 KB Output is correct
14 Correct 651 ms 299604 KB Output is correct
15 Correct 651 ms 299344 KB Output is correct
16 Correct 662 ms 299600 KB Output is correct
17 Correct 612 ms 295300 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 150108 KB Output is correct
2 Correct 42 ms 150100 KB Output is correct
3 Correct 43 ms 150108 KB Output is correct
4 Correct 43 ms 150100 KB Output is correct
5 Correct 43 ms 150096 KB Output is correct
6 Correct 43 ms 150100 KB Output is correct
7 Correct 43 ms 150100 KB Output is correct
8 Correct 42 ms 150096 KB Output is correct
9 Correct 42 ms 150100 KB Output is correct
10 Correct 49 ms 151124 KB Output is correct
11 Correct 51 ms 151092 KB Output is correct
12 Correct 61 ms 150964 KB Output is correct
13 Correct 49 ms 151124 KB Output is correct
14 Correct 49 ms 151008 KB Output is correct
15 Correct 49 ms 151120 KB Output is correct
16 Correct 720 ms 289120 KB Output is correct
17 Correct 604 ms 300116 KB Output is correct
18 Correct 609 ms 297556 KB Output is correct
19 Correct 635 ms 295872 KB Output is correct
20 Correct 597 ms 295984 KB Output is correct
21 Correct 637 ms 297292 KB Output is correct
22 Correct 609 ms 295696 KB Output is correct
23 Correct 507 ms 299852 KB Output is correct
24 Correct 525 ms 295848 KB Output is correct
25 Correct 464 ms 295868 KB Output is correct
26 Correct 477 ms 295612 KB Output is correct
27 Correct 504 ms 295100 KB Output is correct
28 Correct 657 ms 299460 KB Output is correct
29 Correct 651 ms 299604 KB Output is correct
30 Correct 651 ms 299344 KB Output is correct
31 Correct 662 ms 299600 KB Output is correct
32 Correct 612 ms 295300 KB Output is correct
33 Correct 764 ms 298580 KB Output is correct
34 Correct 268 ms 190304 KB Output is correct
35 Correct 764 ms 301296 KB Output is correct
36 Correct 709 ms 298320 KB Output is correct
37 Correct 734 ms 300368 KB Output is correct
38 Correct 704 ms 298580 KB Output is correct
39 Correct 674 ms 303064 KB Output is correct
40 Correct 656 ms 304460 KB Output is correct
41 Correct 599 ms 298584 KB Output is correct
42 Correct 565 ms 295840 KB Output is correct
43 Correct 656 ms 304472 KB Output is correct
44 Correct 634 ms 299856 KB Output is correct
45 Correct 584 ms 301264 KB Output is correct
46 Correct 580 ms 301652 KB Output is correct
47 Correct 650 ms 299520 KB Output is correct
48 Correct 663 ms 299468 KB Output is correct
49 Correct 696 ms 299600 KB Output is correct
50 Correct 630 ms 299472 KB Output is correct
51 Correct 620 ms 305336 KB Output is correct
52 Correct 604 ms 305144 KB Output is correct