oj.uz

Submission #404358

# Submission time Handle Problem Language Result Execution time Memory
404358 2021-05-14T09:17:19 Z SeDunion Werewolf (IOI18_werewolf) C++17
100 / 100
 1220 ms 259128 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 11;
int N, Q, M;

int P[MAXN], sz, par[MAXN], val[MAXN], go[MAXN][2];
int getP(int a) {
	if (a == P[a]) return a;
	return P[a] = getP(P[a]);
}
vector<int>g[MAXN];

int L[MAXN], R[MAXN];

vector<int>G[2];

const int LOG = 20;
int up[MAXN][LOG];

void dfs(int v, int t) {
	if (up[v][0] == 0) up[v][0] = v;
	for (int i = 1 ; i < LOG ; ++ i) up[v][i] = up[up[v][i - 1]][i - 1];
	if (!go[v][0] && !go[v][1]) {
		L[v] = R[v] = G[t].size();
		cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
		G[t].emplace_back(v);
		return;
	}
	up[go[v][0]][0] = up[go[v][1]][0] = v;
	dfs(go[v][0], t);
	dfs(go[v][1], t);
	L[v] = L[go[v][0]];
	R[v] = R[go[v][1]];
	cerr << v << " " << t << " " << L[v] << " " << R[v] << endl;
}

vector<int>tv[MAXN << 2];

void build(int l = 0, int r = N, int v = 1) {
	if (r - l == 1) {
		tv[v] = {G[0][l]};
		return;
	}
	int m = (l + r) >> 1;
	build(l, m, v << 1), build(m, r, v<<1|1);
	tv[v].resize(r - l);
	merge(tv[v << 1].begin(), tv[v << 1].end(), tv[v<<1|1].begin(), tv[v<<1|1].end(),
		tv[v].begin());
}

bool get(int L, int R, int x, int y, int l = 0, int r = N, int v = 1) {
	if (L >= r || l >= R) return 0;
	if (L <= l && r <= R) {
		if (tv[v].back() < x) return 0;
		return *lower_bound(tv[v].begin(), tv[v].end(), x) <= y;
	}
	int m = (l + r) >> 1;
	if (get(L, R, x, y, l, m, v << 1)) return 1;
	if (get(L, R, x, y, m, r, v<<1|1)) return 1;
	return 0;
}

vector<int> check_validity(int N_, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> Lq, vector<int> Rq) {
	N = N_;
	M = X.size();
	Q = S.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[X[i]].emplace_back(Y[i]);
		g[Y[i]].emplace_back(X[i]);
	}
	sz = N;
	for (int i = 0 ; i < N ; ++ i) P[i] = i;
	for (int i = 0 ; i < N ; ++ i) {
		for (int j : g[i]) if (j < i) {
			int x = getP(i);
			int y = getP(j);
			if (x != y) {
				P[x] = P[y] = P[sz] = sz;
				go[sz][0] = x, go[sz][1] = y;
				par[x] = par[y] = sz;
				val[sz] = i;
				sz++;
			}
		}
	}
	dfs(sz-1, 0);
	int off = sz;
	for (int i = 0 ; i < N ; ++ i) P[i+off] = i+off;
	sz += N;
	for (int i = N-1 ; i >= 0 ; -- i) {
		for (int j : g[i]) if (j > i) {
			int x = getP(i+off);
			int y = getP(j+off);
			if (x != y) {
				P[x] = P[y] = P[sz] = sz;
				go[sz][0] = x, go[sz][1] = y;
				par[x] = par[y] = sz;
				val[sz] = i;
				sz++;
			}
		}
	}
	dfs(sz-1, 1);
	for (int &i : G[1]) i -= off;
	for (int i : G[0]) cerr << i << " ";
	cerr << ": G[0]\n";
	for (int i : G[1]) cerr << i << " ";
	cerr << ": G[1]\n";
	vector<int>id(N);
	for (int i = 0 ; i < N ; ++ i) {
		id[G[1][i]] = i;
		G[1][i] = i;
	}
	for (int i = 0 ; i < N ; ++ i) {
		G[0][i] = id[G[0][i]];
	}
	for (int i : G[0]) cerr << i << " ";
	cerr << ": G[0]\n";
	for (int i : G[1]) cerr << i << " ";
	cerr << ": G[1]\n";
	build();
	vector<int>ANS(Q);
	for (int q = 0 ; q < Q ; ++ q) {
		int Ls, Rs, Le, Re;
		{
			int v = E[q];
			for (int i = LOG - 1 ; i >= 0 ; -- i) {
				if (val[up[v][i]] <= Rq[q]) v = up[v][i];
			}
			Le = L[v], Re = R[v];
		}
		{
			int v = S[q] + off;
			for (int i = LOG - 1 ; i >= 0 ; -- i) {
				if (val[up[v][i]] >= Lq[q]) v = up[v][i];
			}
			Ls = L[v], Rs = R[v];
		}
		cerr << Ls << " " << Rs << " " << Le << " " << Re << " LR" << endl;
		bool has = false;
		for (int i = Le ; i <= Re ; ++ i) {
			for (int j = Ls ; j <= Rs ; ++ j) {
				if (G[0][i] == G[1][j]) {
					has = true;
				}
			}
		}
		ANS[q] = get(Le, Re + 1, Ls, Rs);
	}
	return ANS;
}

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:147:8: warning: variable 'has' set but not used [-Wunused-but-set-variable]
  147 |   bool has = false;
      |        ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117700 KB Output is correct
2 Correct 63 ms 117696 KB Output is correct
3 Correct 66 ms 117780 KB Output is correct
4 Correct 64 ms 117696 KB Output is correct
5 Correct 62 ms 117744 KB Output is correct
6 Correct 63 ms 117792 KB Output is correct
7 Correct 64 ms 117804 KB Output is correct
8 Correct 63 ms 117748 KB Output is correct
9 Correct 62 ms 117800 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117700 KB Output is correct
2 Correct 63 ms 117696 KB Output is correct
3 Correct 66 ms 117780 KB Output is correct
4 Correct 64 ms 117696 KB Output is correct
5 Correct 62 ms 117744 KB Output is correct
6 Correct 63 ms 117792 KB Output is correct
7 Correct 64 ms 117804 KB Output is correct
8 Correct 63 ms 117748 KB Output is correct
9 Correct 62 ms 117800 KB Output is correct
10 Correct 70 ms 119604 KB Output is correct
11 Correct 72 ms 119576 KB Output is correct
12 Correct 70 ms 119548 KB Output is correct
13 Correct 78 ms 119588 KB Output is correct
14 Correct 71 ms 119632 KB Output is correct
15 Correct 72 ms 119600 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 240212 KB Output is correct
2 Correct 998 ms 244888 KB Output is correct
3 Correct 861 ms 250308 KB Output is correct
4 Correct 834 ms 248888 KB Output is correct
5 Correct 865 ms 248852 KB Output is correct
6 Correct 954 ms 248760 KB Output is correct
7 Correct 843 ms 248632 KB Output is correct
8 Correct 910 ms 253300 KB Output is correct
9 Correct 755 ms 250320 KB Output is correct
10 Correct 601 ms 248908 KB Output is correct
11 Correct 628 ms 248848 KB Output is correct
12 Correct 730 ms 248708 KB Output is correct
13 Correct 1078 ms 253440 KB Output is correct
14 Correct 1113 ms 253412 KB Output is correct
15 Correct 1101 ms 253320 KB Output is correct
16 Correct 1082 ms 253412 KB Output is correct
17 Correct 833 ms 248712 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117700 KB Output is correct
2 Correct 63 ms 117696 KB Output is correct
3 Correct 66 ms 117780 KB Output is correct
4 Correct 64 ms 117696 KB Output is correct
5 Correct 62 ms 117744 KB Output is correct
6 Correct 63 ms 117792 KB Output is correct
7 Correct 64 ms 117804 KB Output is correct
8 Correct 63 ms 117748 KB Output is correct
9 Correct 62 ms 117800 KB Output is correct
10 Correct 70 ms 119604 KB Output is correct
11 Correct 72 ms 119576 KB Output is correct
12 Correct 70 ms 119548 KB Output is correct
13 Correct 78 ms 119588 KB Output is correct
14 Correct 71 ms 119632 KB Output is correct
15 Correct 72 ms 119600 KB Output is correct
16 Correct 955 ms 240212 KB Output is correct
17 Correct 998 ms 244888 KB Output is correct
18 Correct 861 ms 250308 KB Output is correct
19 Correct 834 ms 248888 KB Output is correct
20 Correct 865 ms 248852 KB Output is correct
21 Correct 954 ms 248760 KB Output is correct
22 Correct 843 ms 248632 KB Output is correct
23 Correct 910 ms 253300 KB Output is correct
24 Correct 755 ms 250320 KB Output is correct
25 Correct 601 ms 248908 KB Output is correct
26 Correct 628 ms 248848 KB Output is correct
27 Correct 730 ms 248708 KB Output is correct
28 Correct 1078 ms 253440 KB Output is correct
29 Correct 1113 ms 253412 KB Output is correct
30 Correct 1101 ms 253320 KB Output is correct
31 Correct 1082 ms 253412 KB Output is correct
32 Correct 833 ms 248712 KB Output is correct
33 Correct 1145 ms 250040 KB Output is correct
34 Correct 419 ms 149712 KB Output is correct
35 Correct 1220 ms 253292 KB Output is correct
36 Correct 1049 ms 249352 KB Output is correct
37 Correct 1169 ms 252404 KB Output is correct
38 Correct 1131 ms 250108 KB Output is correct
39 Correct 1195 ms 258268 KB Output is correct
40 Correct 1179 ms 258452 KB Output is correct
41 Correct 910 ms 251836 KB Output is correct
42 Correct 676 ms 249400 KB Output is correct
43 Correct 1122 ms 257068 KB Output is correct
44 Correct 1170 ms 252520 KB Output is correct
45 Correct 989 ms 258584 KB Output is correct
46 Correct 893 ms 258284 KB Output is correct
47 Correct 1117 ms 253480 KB Output is correct
48 Correct 1090 ms 253364 KB Output is correct
49 Correct 1090 ms 253476 KB Output is correct
50 Correct 1062 ms 253344 KB Output is correct
51 Correct 1069 ms 259088 KB Output is correct
52 Correct 1050 ms 259128 KB Output is correct