oj.uz

Submission #381671

# Submission time Handle Problem Language Result Execution time Memory
381671 2021-03-25T14:42:45 Z LucaDantas Werewolf (IOI18_werewolf) C++17
100 / 100
 1272 ms 242524 KB 
#include "werewolf.h"
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

using pii = pair<int,int>;

#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ff first
#define ss second

constexpr int maxn = 2e6+10, logn = 22;

int n;

struct DSU
{
	int pai[maxn];
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i; }
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i; }
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return 0;
		pai[b] = a;
		return 1;
	}
} dsu;

struct KRT
{
	vector<int> g[maxn]; // graph pointing down
	int tab[maxn][logn], val[maxn], pos[maxn], head = 0, t = 1; // position of leafs

	int in[maxn], out[maxn];

	DSU aux;

	void addEdge(int from, int to, int weight) {
		head = from;
		val[from] = weight;

		to = aux.find(to); // gets the head of the component
		aux.join(from, to); // make him my son

		tab[to][0] = from;
		g[from].pb(to);
	}

	void dfs(int u) {
		if(u <= n) return (void)(pos[u] = in[u] = out[u] = t++);

		in[u] = t;
		for(int v : g[u])
			dfs(v);
		out[u] = t-1;
	}

	void build() {
		dfs(head);

		for(int l = 1; l < logn; l++)
			for(int i = 1; i <= head; i++)
				tab[i][l] = tab[tab[i][l-1]][l-1];
	}

	int get(int u, int v, int k) {
		auto comp = [&](int a, int b) { return k?a>=b:a<=b; };
		for(int l = logn-1; l >= 0; l--) {
			if(tab[u][l] && comp(val[tab[u][l]], v))
				u = tab[u][l];
		}
		return u;
	}

	void get_dfs(int u, vector<int>& vv) {
		if(u <= n) return (void)(vv.pb(u));
		for(int v : g[u])
			get_dfs(v, vv);
	}

	void dfs_debug(int u, int p) {
		// printf("%d %d\n", u, p);
		if(u <= n) printf("(%d %d)\n", u, pos[u]);
		else printf("(%d [%d %d])\n", u, in[u], out[u]);
		for(int v : g[u])
			dfs_debug(v, u);
	}

	void debug() {
		puts("PRINTING THE TREE");
		dfs_debug(head, 0);
	}
} krt[2];

struct Event
{
	int t, x, y1, y2, id;
	bool operator<(Event e) {
		if(x == e.x) return t<e.t; // if I'm a point I must appear before a query
		return x < e.x;
	}
} events[maxn];

struct BIT
{
	int bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int get(int l, int r) { return query(r) - query(l-1); }
} bit;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
	vector<int> S, vector<int> E, vector<int> L, vector<int> R) {

	n = N;

	vector<pii> edges;
	int M = (int)X.size();
	for(int i = 0; i < M; i++) {
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		++X[i], ++Y[i];

		edges.pb({X[i], Y[i]});
	}


	{
		sort(all(edges), [](pii a, pii b) {
			return a.first > b.first;
		});

		int cnt = N;
		for(int i = 0; i < M; i++) {
			int a = edges[i].ff, b = edges[i].ss;
			// puts("OI");
			if(dsu.join(a, b)) {
				// printf("%d %d\n", a, b);
				++cnt;
				krt[0].addEdge(cnt, a, a); // from, to, value of new node
				krt[0].addEdge(cnt, b, a);
			}
		}

		krt[0].build();

		// krt[0].debug();
	}

	{
		dsu.init();

		// Sort by increasing big value
		sort(all(edges), [](pii a, pii b) {
			return a.ss < b.ss;
		});

		int cnt = N;
		for(int i = 0; i < M; i++) {
			int a = edges[i].ff, b = edges[i].ss;
			if(dsu.join(a, b)) {
				++cnt;
				krt[1].addEdge(cnt, a, b);
				krt[1].addEdge(cnt, b, b);
			}
		}

		krt[1].build();

		// krt[1].debug();
	}

	int Q = S.size();

	vector<int> ans(Q);

	for(int i = 1; i <= N; i++)
		events[i] = {0, krt[0].pos[i], krt[1].pos[i], -1, -1};

	for(int i = 0; i < Q; i++) {
		if(S[i] < L[i] || E[i] > R[i]) ans[i] = -2*maxn;

		++S[i], ++E[i], ++L[i], ++R[i];

		int p1 = krt[0].get(S[i], L[i], 1);
		int p2 = krt[1].get(E[i], R[i], 0);

		// printf("%d %d %d\n", i, p1, p2);


		events[N+2*i+1] = {-1, krt[0].in[p1], krt[1].in[p2], krt[1].out[p2], i},
		events[N+2*i+2] = {1, krt[0].out[p1], krt[1].in[p2], krt[1].out[p2], i};
	}

	// puts("");

	// sort(events+1, events+N+1);
	sort(events+1, events+N+2*Q+1);

	// for(int i = 1; i <= N; i++) {
	for(int i = 1; i <= N+2*Q; i++) {
		Event e = events[i];
		// printf("%d %d %d %d %d\n", e.t, e.x, e.y1, e.y2, e.id);
		if(e.t == 0) bit.upd(e.y1, 1);
		else ans[e.id] += e.t * bit.get(e.y1, e.y2);
	}

	// puts("");

	for(int i = 0; i < Q; i++)
		ans[i] = ans[i]>0;
		// printf("%d ", ans[i]), ans[i] = ans[i]>0;
	// printf("\n");

	return ans;
	// return vector<int>(0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117868 KB Output is correct
2 Correct 74 ms 117996 KB Output is correct
3 Correct 72 ms 117868 KB Output is correct
4 Correct 72 ms 117868 KB Output is correct
5 Correct 72 ms 117868 KB Output is correct
6 Correct 72 ms 117868 KB Output is correct
7 Correct 72 ms 117868 KB Output is correct
8 Correct 72 ms 117868 KB Output is correct
9 Correct 72 ms 117868 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117868 KB Output is correct
2 Correct 74 ms 117996 KB Output is correct
3 Correct 72 ms 117868 KB Output is correct
4 Correct 72 ms 117868 KB Output is correct
5 Correct 72 ms 117868 KB Output is correct
6 Correct 72 ms 117868 KB Output is correct
7 Correct 72 ms 117868 KB Output is correct
8 Correct 72 ms 117868 KB Output is correct
9 Correct 72 ms 117868 KB Output is correct
10 Correct 79 ms 119660 KB Output is correct
11 Correct 83 ms 119532 KB Output is correct
12 Correct 78 ms 119660 KB Output is correct
13 Correct 80 ms 119916 KB Output is correct
14 Correct 79 ms 119788 KB Output is correct
15 Correct 80 ms 119660 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 233032 KB Output is correct
2 Correct 1142 ms 237788 KB Output is correct
3 Correct 985 ms 234716 KB Output is correct
4 Correct 900 ms 233232 KB Output is correct
5 Correct 906 ms 233308 KB Output is correct
6 Correct 958 ms 233052 KB Output is correct
7 Correct 926 ms 233052 KB Output is correct
8 Correct 1071 ms 237712 KB Output is correct
9 Correct 816 ms 234904 KB Output is correct
10 Correct 739 ms 233328 KB Output is correct
11 Correct 749 ms 233436 KB Output is correct
12 Correct 799 ms 233180 KB Output is correct
13 Correct 1208 ms 237788 KB Output is correct
14 Correct 1194 ms 237712 KB Output is correct
15 Correct 1180 ms 237684 KB Output is correct
16 Correct 1176 ms 237788 KB Output is correct
17 Correct 924 ms 233052 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 117868 KB Output is correct
2 Correct 74 ms 117996 KB Output is correct
3 Correct 72 ms 117868 KB Output is correct
4 Correct 72 ms 117868 KB Output is correct
5 Correct 72 ms 117868 KB Output is correct
6 Correct 72 ms 117868 KB Output is correct
7 Correct 72 ms 117868 KB Output is correct
8 Correct 72 ms 117868 KB Output is correct
9 Correct 72 ms 117868 KB Output is correct
10 Correct 79 ms 119660 KB Output is correct
11 Correct 83 ms 119532 KB Output is correct
12 Correct 78 ms 119660 KB Output is correct
13 Correct 80 ms 119916 KB Output is correct
14 Correct 79 ms 119788 KB Output is correct
15 Correct 80 ms 119660 KB Output is correct
16 Correct 1000 ms 233032 KB Output is correct
17 Correct 1142 ms 237788 KB Output is correct
18 Correct 985 ms 234716 KB Output is correct
19 Correct 900 ms 233232 KB Output is correct
20 Correct 906 ms 233308 KB Output is correct
21 Correct 958 ms 233052 KB Output is correct
22 Correct 926 ms 233052 KB Output is correct
23 Correct 1071 ms 237712 KB Output is correct
24 Correct 816 ms 234904 KB Output is correct
25 Correct 739 ms 233328 KB Output is correct
26 Correct 749 ms 233436 KB Output is correct
27 Correct 799 ms 233180 KB Output is correct
28 Correct 1208 ms 237788 KB Output is correct
29 Correct 1194 ms 237712 KB Output is correct
30 Correct 1180 ms 237684 KB Output is correct
31 Correct 1176 ms 237788 KB Output is correct
32 Correct 924 ms 233052 KB Output is correct
33 Correct 1155 ms 234180 KB Output is correct
34 Correct 485 ms 142884 KB Output is correct
35 Correct 1243 ms 237532 KB Output is correct
36 Correct 1111 ms 233820 KB Output is correct
37 Correct 1229 ms 236628 KB Output is correct
38 Correct 1145 ms 234348 KB Output is correct
39 Correct 1111 ms 242420 KB Output is correct
40 Correct 1221 ms 240212 KB Output is correct
41 Correct 1012 ms 235996 KB Output is correct
42 Correct 860 ms 233692 KB Output is correct
43 Correct 1272 ms 240468 KB Output is correct
44 Correct 1182 ms 236636 KB Output is correct
45 Correct 966 ms 242524 KB Output is correct
46 Correct 976 ms 242524 KB Output is correct
47 Correct 1180 ms 238044 KB Output is correct
48 Correct 1198 ms 237660 KB Output is correct
49 Correct 1200 ms 238044 KB Output is correct
50 Correct 1212 ms 237784 KB Output is correct
51 Correct 1130 ms 240340 KB Output is correct
52 Correct 1135 ms 240452 KB Output is correct