oj.uz

Submission #96832

# Submission time Handle Problem Language Result Execution time Memory
96832 2019-02-12T12:06:41 Z youngyojun Werewolf (IOI18_werewolf) C++11
100 / 100
 1946 ms 114752 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;

const int MAXN = 200055;
const int MAXM = 400055;
const int MAXQ = 200055;

struct TRE {
	vector<int> G[MAXN];
	int prt[18][MAXN], cnt[MAXN], dfo[MAXN];
	int N, Rt;

	void add(int p, int v) { G[p].eb(v); }
	void dfs(int i, int &c) {
		cnt[i] = 1; dfo[i] = c++;
		for(int v : G[i]) {
			prt[0][v] = i;
			dfs(v, c);
			cnt[i] += cnt[v];
		}
	}
		
	void run() {
		prt[0][Rt] = N;
		for(int i = 18; i--;) prt[i][N] = N;
		{ int _ = 0; dfs(Rt, _); }
		for(int j = 1; j < 18; j++) for(int i = 0; i < N; i++)
			prt[j][i] = prt[j-1][prt[j-1][i]];
	}
} TA, TB;

struct BIT {
	int d[MAXN];
	void upd(int x) {
		for(x += 5; x < MAXN; x += rb(x)) d[x]++;
	}
	int get(int x) {
		int r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

struct EVT {
	EVT(int idx, int x, int y, bool inv)
		: idx(idx), x(x), y(y), inv(inv) {}
	int idx, x, y;
	bool inv;
	bool operator < (const EVT &t) const {
		if(x != t.x) return x < t.x;
		return idx < t.idx;
	}
};
vector<EVT> EV;

vector<int> G[MAXN];
int ud[MAXN];

int A[MAXM], B[MAXM];
int CS[MAXQ], CE[MAXQ], L[MAXQ], R[MAXQ];
int Ans[MAXQ];

int N, M, Q;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

int getMx(int v, int c) {
	for(int i = 18, p; i--;) {
		p = TA.prt[i][v];
		if(p <= c) v = p;
	}
	return v;
}
int getMn(int v, int c) {
	for(int i = 18, p; i--;) {
		p = TB.prt[i][v];
		if(c <= p && p < N) v = p;
	}
	return v;
}

void getAns() {
	for(int i = 0, a, b; i < M; i++) {
		a = A[i]; b = B[i];
		G[a].eb(b); G[b].eb(a);
	}
	TA.N = TB.N = N; TA.Rt = N-1;
	iota(ud, ud+N, 0);
	for(int i = 1; i < N; i++) for(int v : G[i]) {
		if(i < v) continue;
		v = uf(v);
		if(v != i) TA.add(i, v);
		uf(i, v);
	}
	iota(ud, ud+N, 0);
	for(int i = N; i--;) for(int v : G[i]) {
		if(v < i) continue;
		v = uf(v);
		if(v != i) TB.add(i, uf(v));
		uf(i, v);
	}
	TA.run(); TB.run();

	for(int i = 0; i < N; i++)
		EV.eb(-1, TA.dfo[i], TB.dfo[i], false);
	for(int i = 0, a, b; i < Q; i++) {
		a = getMx(CE[i], R[i]);
		b = getMn(CS[i], L[i]);
		EV.eb(i, TA.dfo[a]-1, TB.dfo[b]-1, true);
		EV.eb(i, TA.dfo[a]-1, TB.dfo[b]+TB.cnt[b]-1, false);
		a = TA.dfo[a]+TA.cnt[a]-1;
		EV.eb(i, a, TB.dfo[b]-1, false);
		EV.eb(i, a, TB.dfo[b]+TB.cnt[b]-1, true);
	}
	sorv(EV);
	for(auto &ev : EV) {
		if(ev.idx < 0) bit.upd(ev.y);
		else Ans[ev.idx] += bit.get(ev.y) * (ev.inv ? -1 : 1);
	}
}

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) {
	::N = N; ::M = sz(X); ::Q = sz(S);
	for(int i = 0; i < M; i++) { ::A[i] = X[i]; ::B[i] = Y[i]; }
	for(int i = 0; i < Q; i++) {
		::CS[i] = S[i]; ::CE[i] = E[i];
		::L[i] = L[i]; ::R[i] = R[i];
	}
	getAns();
	vector<int> V;
	for(int i = 0; i < Q; i++) V.eb(!!Ans[i]);
	return V;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14848 KB Output is correct
2 Correct 17 ms 14720 KB Output is correct
3 Correct 18 ms 14848 KB Output is correct
4 Correct 16 ms 14720 KB Output is correct
5 Correct 16 ms 14848 KB Output is correct
6 Correct 18 ms 14848 KB Output is correct
7 Correct 15 ms 14840 KB Output is correct
8 Correct 16 ms 14720 KB Output is correct
9 Correct 16 ms 14848 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14848 KB Output is correct
2 Correct 17 ms 14720 KB Output is correct
3 Correct 18 ms 14848 KB Output is correct
4 Correct 16 ms 14720 KB Output is correct
5 Correct 16 ms 14848 KB Output is correct
6 Correct 18 ms 14848 KB Output is correct
7 Correct 15 ms 14840 KB Output is correct
8 Correct 16 ms 14720 KB Output is correct
9 Correct 16 ms 14848 KB Output is correct
10 Correct 24 ms 16248 KB Output is correct
11 Correct 26 ms 16252 KB Output is correct
12 Correct 25 ms 16128 KB Output is correct
13 Correct 24 ms 16232 KB Output is correct
14 Correct 26 ms 16376 KB Output is correct
15 Correct 27 ms 16372 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 102880 KB Output is correct
2 Correct 1262 ms 105344 KB Output is correct
3 Correct 1107 ms 103628 KB Output is correct
4 Correct 1174 ms 103088 KB Output is correct
5 Correct 1165 ms 102836 KB Output is correct
6 Correct 1258 ms 102924 KB Output is correct
7 Correct 1360 ms 102872 KB Output is correct
8 Correct 1115 ms 105284 KB Output is correct
9 Correct 828 ms 103724 KB Output is correct
10 Correct 922 ms 103028 KB Output is correct
11 Correct 1050 ms 102960 KB Output is correct
12 Correct 1066 ms 102948 KB Output is correct
13 Correct 1946 ms 110312 KB Output is correct
14 Correct 1744 ms 110276 KB Output is correct
15 Correct 1747 ms 110356 KB Output is correct
16 Correct 1765 ms 110300 KB Output is correct
17 Correct 1158 ms 102852 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14848 KB Output is correct
2 Correct 17 ms 14720 KB Output is correct
3 Correct 18 ms 14848 KB Output is correct
4 Correct 16 ms 14720 KB Output is correct
5 Correct 16 ms 14848 KB Output is correct
6 Correct 18 ms 14848 KB Output is correct
7 Correct 15 ms 14840 KB Output is correct
8 Correct 16 ms 14720 KB Output is correct
9 Correct 16 ms 14848 KB Output is correct
10 Correct 24 ms 16248 KB Output is correct
11 Correct 26 ms 16252 KB Output is correct
12 Correct 25 ms 16128 KB Output is correct
13 Correct 24 ms 16232 KB Output is correct
14 Correct 26 ms 16376 KB Output is correct
15 Correct 27 ms 16372 KB Output is correct
16 Correct 1210 ms 102880 KB Output is correct
17 Correct 1262 ms 105344 KB Output is correct
18 Correct 1107 ms 103628 KB Output is correct
19 Correct 1174 ms 103088 KB Output is correct
20 Correct 1165 ms 102836 KB Output is correct
21 Correct 1258 ms 102924 KB Output is correct
22 Correct 1360 ms 102872 KB Output is correct
23 Correct 1115 ms 105284 KB Output is correct
24 Correct 828 ms 103724 KB Output is correct
25 Correct 922 ms 103028 KB Output is correct
26 Correct 1050 ms 102960 KB Output is correct
27 Correct 1066 ms 102948 KB Output is correct
28 Correct 1946 ms 110312 KB Output is correct
29 Correct 1744 ms 110276 KB Output is correct
30 Correct 1747 ms 110356 KB Output is correct
31 Correct 1765 ms 110300 KB Output is correct
32 Correct 1158 ms 102852 KB Output is correct
33 Correct 1152 ms 103052 KB Output is correct
34 Correct 502 ms 68188 KB Output is correct
35 Correct 1520 ms 105552 KB Output is correct
36 Correct 1312 ms 103492 KB Output is correct
37 Correct 1586 ms 104572 KB Output is correct
38 Correct 1510 ms 104080 KB Output is correct
39 Correct 1794 ms 110912 KB Output is correct
40 Correct 1653 ms 114752 KB Output is correct
41 Correct 929 ms 104148 KB Output is correct
42 Correct 1088 ms 103380 KB Output is correct
43 Correct 1687 ms 110912 KB Output is correct
44 Correct 1193 ms 104688 KB Output is correct
45 Correct 809 ms 111172 KB Output is correct
46 Correct 1193 ms 110948 KB Output is correct
47 Correct 1617 ms 110628 KB Output is correct
48 Correct 1210 ms 110284 KB Output is correct
49 Correct 1254 ms 110528 KB Output is correct
50 Correct 1154 ms 110424 KB Output is correct
51 Correct 1052 ms 114676 KB Output is correct
52 Correct 1392 ms 114648 KB Output is correct