oj.uz

Submission #404354

# Submission time Handle Problem Language Result Execution time Memory
404354 2021-05-14T09:12:49 Z SeDunion Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 190624 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];

void dfs(int v, int t) {
	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;
	}
	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];
			while (par[v] && val[par[v]] <= Rq[q]) v = par[v];
			Le = L[v], Re = R[v];
		}
		{
			int v = S[q] + off;
			while (par[v] && val[par[v]] >= Lq[q]) v = par[v];
			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:137:8: warning: variable 'has' set but not used [-Wunused-but-set-variable]
  137 |   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 62 ms 117720 KB Output is correct
3 Correct 63 ms 117660 KB Output is correct
4 Correct 70 ms 117652 KB Output is correct
5 Correct 64 ms 117716 KB Output is correct
6 Correct 64 ms 117704 KB Output is correct
7 Correct 64 ms 117700 KB Output is correct
8 Correct 63 ms 117800 KB Output is correct
9 Correct 64 ms 117648 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 62 ms 117720 KB Output is correct
3 Correct 63 ms 117660 KB Output is correct
4 Correct 70 ms 117652 KB Output is correct
5 Correct 64 ms 117716 KB Output is correct
6 Correct 64 ms 117704 KB Output is correct
7 Correct 64 ms 117700 KB Output is correct
8 Correct 63 ms 117800 KB Output is correct
9 Correct 64 ms 117648 KB Output is correct
10 Correct 78 ms 118724 KB Output is correct
11 Correct 72 ms 118820 KB Output is correct
12 Correct 68 ms 118572 KB Output is correct
13 Correct 77 ms 118780 KB Output is correct
14 Correct 78 ms 118724 KB Output is correct
15 Correct 77 ms 118752 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 185960 KB Output is correct
2 Execution timed out 4070 ms 190624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 117700 KB Output is correct
2 Correct 62 ms 117720 KB Output is correct
3 Correct 63 ms 117660 KB Output is correct
4 Correct 70 ms 117652 KB Output is correct
5 Correct 64 ms 117716 KB Output is correct
6 Correct 64 ms 117704 KB Output is correct
7 Correct 64 ms 117700 KB Output is correct
8 Correct 63 ms 117800 KB Output is correct
9 Correct 64 ms 117648 KB Output is correct
10 Correct 78 ms 118724 KB Output is correct
11 Correct 72 ms 118820 KB Output is correct
12 Correct 68 ms 118572 KB Output is correct
13 Correct 77 ms 118780 KB Output is correct
14 Correct 78 ms 118724 KB Output is correct
15 Correct 77 ms 118752 KB Output is correct
16 Correct 671 ms 185960 KB Output is correct
17 Execution timed out 4070 ms 190624 KB Time limit exceeded
18 Halted 0 ms 0 KB -