oj.uz

Submission #580868

# Submission time Handle Problem Language Result Execution time Memory
580868 2022-06-22T03:37:52 Z 8e7 Werewolf (IOI18_werewolf) C++17
100 / 100
 886 ms 101940 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
#include "werewolf.h"
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
vector<int> adj[maxn], tr[maxn * 2];
vector<int> qi[maxn * 2];
pii ran[maxn];

struct query{
	int s, e, l, r, id;
	query(){s = e = l = r = id = 0;}		
	query(int a, int b, int c, int d, int p) {
		s = a, e = b, l = c, r = d, id = p;
	}
};
struct DSU{
	int id[maxn], par[maxn];
	int cur = 0;
	void init(int n) {
		cur = n;
		for (int i = 0;i < n;i++) {
			id[i] = i;
			par[i] = i;
		}
	}
	int find(int a) {
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return 0;
		tr[cur].push_back(id[a]);
		tr[cur].push_back(id[b]);
		par[b] = a;	
		id[a] = cur;
		cur++;
		return 1;
	}
} d;

set<int> se[maxn];
void combine(int u, int v) {
	if (se[u].size() < se[v].size()) swap(se[u], se[v]);
	for (int p:se[v]) {
		se[u].insert(p);
	}
	se[v].clear();
}
int cor[maxn];
int C = 0;
pii dfs(int n) {
	pii ret = {inf, -1};
	for (int v:tr[n]) {
		pii tmp = dfs(v);
		ret = {min(tmp.ff, ret.ff), max(tmp.ss, ret.ss)};
	}
	if (!tr[n].size()) {
		cor[n] = C++;
		ret = {cor[n], cor[n]};
	}
	for (int i:qi[n]) ran[i] = ret;
	//debug(n, ret.ff, ret.ss);
	return ret;
}

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) {
	
	vector<query> que;
	int Q = S.size(), M = X.size();

	for (int i = 0;i < Q;i++) {
		if (S[i] >= L[i] && E[i] <= R[i]) {
			que.push_back(query(S[i], E[i], L[i], R[i], i));
		}
	}	
	sort(que.begin(), que.end(), [&] (query x, query y){return x.r < y.r;});
	vector<int> ret(Q, 0);	
	for (int i = 0;i < M;i++) {
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}	
	d.init(N);

	{
		int ind = 0;
		for (int i = 0;i < N;i++) {
			for (int j:adj[i]) {
				if (j < i) {
					d.Union(i, j);
				}
			}
			while (ind < Q && que[ind].r == i) {
				int pos = d.id[d.find(que[ind].e)];
				qi[pos].push_back(que[ind].id);		
				ind++;
			}
		}
	}
	dfs(d.cur - 1);
	sort(que.begin(), que.end(), [&] (query x, query y){return x.l > y.l;});
	{
		d.init(N);
		for (int i = 0;i < N;i++) se[i].insert(cor[i]);
		int ind = 0;
		for (int i = N - 1;i >= 0;i--) {
			for (int j:adj[i]) {
				if (j > i) {
					if (d.find(i) != d.find(j)) {
						combine(d.find(i), d.find(j));
						d.Union(i, j);
					}
				}
			}
			/*
			debug("se", i);
			for (int j = 0;j < N;j++) {
				pary(se[j].begin(), se[j].end());
			}
			debug();
			*/
			while (ind < Q && que[ind].l == i) {
				int p = d.find(que[ind].s);		
				int id = que[ind].id;
				if (se[p].lower_bound(ran[id].ff) != se[p].upper_bound(ran[id].ss)) {
					ret[id] = 1;
				}
				ind++;
			}
		}
	}
	return ret;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 5 3 4
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33108 KB Output is correct
2 Correct 16 ms 33208 KB Output is correct
3 Correct 18 ms 33108 KB Output is correct
4 Correct 20 ms 33288 KB Output is correct
5 Correct 18 ms 33224 KB Output is correct
6 Correct 18 ms 33212 KB Output is correct
7 Correct 18 ms 33124 KB Output is correct
8 Correct 17 ms 33108 KB Output is correct
9 Correct 16 ms 33108 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33108 KB Output is correct
2 Correct 16 ms 33208 KB Output is correct
3 Correct 18 ms 33108 KB Output is correct
4 Correct 20 ms 33288 KB Output is correct
5 Correct 18 ms 33224 KB Output is correct
6 Correct 18 ms 33212 KB Output is correct
7 Correct 18 ms 33124 KB Output is correct
8 Correct 17 ms 33108 KB Output is correct
9 Correct 16 ms 33108 KB Output is correct
10 Correct 21 ms 33896 KB Output is correct
11 Correct 21 ms 33828 KB Output is correct
12 Correct 23 ms 33792 KB Output is correct
13 Correct 23 ms 34112 KB Output is correct
14 Correct 29 ms 34060 KB Output is correct
15 Correct 23 ms 33932 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 78776 KB Output is correct
2 Correct 655 ms 83000 KB Output is correct
3 Correct 725 ms 77348 KB Output is correct
4 Correct 815 ms 75856 KB Output is correct
5 Correct 719 ms 75884 KB Output is correct
6 Correct 833 ms 78244 KB Output is correct
7 Correct 790 ms 78504 KB Output is correct
8 Correct 617 ms 82880 KB Output is correct
9 Correct 555 ms 77364 KB Output is correct
10 Correct 610 ms 75068 KB Output is correct
11 Correct 675 ms 75340 KB Output is correct
12 Correct 711 ms 77044 KB Output is correct
13 Correct 551 ms 88572 KB Output is correct
14 Correct 539 ms 88556 KB Output is correct
15 Correct 530 ms 88592 KB Output is correct
16 Correct 639 ms 88528 KB Output is correct
17 Correct 796 ms 78396 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33108 KB Output is correct
2 Correct 16 ms 33208 KB Output is correct
3 Correct 18 ms 33108 KB Output is correct
4 Correct 20 ms 33288 KB Output is correct
5 Correct 18 ms 33224 KB Output is correct
6 Correct 18 ms 33212 KB Output is correct
7 Correct 18 ms 33124 KB Output is correct
8 Correct 17 ms 33108 KB Output is correct
9 Correct 16 ms 33108 KB Output is correct
10 Correct 21 ms 33896 KB Output is correct
11 Correct 21 ms 33828 KB Output is correct
12 Correct 23 ms 33792 KB Output is correct
13 Correct 23 ms 34112 KB Output is correct
14 Correct 29 ms 34060 KB Output is correct
15 Correct 23 ms 33932 KB Output is correct
16 Correct 886 ms 78776 KB Output is correct
17 Correct 655 ms 83000 KB Output is correct
18 Correct 725 ms 77348 KB Output is correct
19 Correct 815 ms 75856 KB Output is correct
20 Correct 719 ms 75884 KB Output is correct
21 Correct 833 ms 78244 KB Output is correct
22 Correct 790 ms 78504 KB Output is correct
23 Correct 617 ms 82880 KB Output is correct
24 Correct 555 ms 77364 KB Output is correct
25 Correct 610 ms 75068 KB Output is correct
26 Correct 675 ms 75340 KB Output is correct
27 Correct 711 ms 77044 KB Output is correct
28 Correct 551 ms 88572 KB Output is correct
29 Correct 539 ms 88556 KB Output is correct
30 Correct 530 ms 88592 KB Output is correct
31 Correct 639 ms 88528 KB Output is correct
32 Correct 796 ms 78396 KB Output is correct
33 Correct 829 ms 79236 KB Output is correct
34 Correct 315 ms 70576 KB Output is correct
35 Correct 767 ms 91940 KB Output is correct
36 Correct 783 ms 86020 KB Output is correct
37 Correct 854 ms 90648 KB Output is correct
38 Correct 798 ms 87080 KB Output is correct
39 Correct 705 ms 100720 KB Output is correct
40 Correct 806 ms 98188 KB Output is correct
41 Correct 775 ms 88404 KB Output is correct
42 Correct 739 ms 84172 KB Output is correct
43 Correct 851 ms 95844 KB Output is correct
44 Correct 713 ms 89416 KB Output is correct
45 Correct 638 ms 101940 KB Output is correct
46 Correct 747 ms 101904 KB Output is correct
47 Correct 490 ms 97168 KB Output is correct
48 Correct 485 ms 96944 KB Output is correct
49 Correct 511 ms 97076 KB Output is correct
50 Correct 520 ms 96944 KB Output is correct
51 Correct 618 ms 98996 KB Output is correct
52 Correct 641 ms 99036 KB Output is correct