oj.uz

Submission #155901

# Submission time Handle Problem Language Result Execution time Memory
155901 2019-10-02T00:48:52 Z imyujin Werewolf (IOI18_werewolf) C++17
100 / 100
 881 ms 94620 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define eb emplace_back
#define all(v) ((v).begin()),((v).end())
#define fi first
#define se second
#define rb(x) ((x)&(-(x)))

const int MAXN = 200010;
const int MX = 1 << 18;
int N;

struct SEG {
	int seg[2 * MX];

	void mkseg(int idx, int l, int r, vector<int> &e) {
		if(l == r) seg[idx] = e[l];
		else {
			int m = (l + r) / 2;
			mkseg(idx * 2, l, m, e);
			mkseg(idx * 2 + 1, m + 1, r, e);
			seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
		}
	}
	void init(vector<int> &e) { mkseg(1, 0, e.size() - 1, e); }

	int gseg(int idx, int l, int r, int x, int z) {
		if(x < l) return l - 1;
		//if(idx == 1) printf("gseg(x = %d, z = %d)\n", x, z);
		if(seg[idx] >= z) return l - 1;
		if(l == r) return l;
		int m = (l + r) / 2;
		if(x > m) {
			int t = gseg(idx * 2 + 1, m + 1, r, x, z);
			if(t > m) return t;
		}
		return gseg(idx * 2, l, m, x, z);
	}
};

struct TREE {
	vector<pii> ed;
	int uni[MAXN];
	vector<int> v[MAXN], e[MAXN];
	int dn[MAXN];
	SEG seg, segr;

	int guni(int x) { return uni[x] == x ? x : uni[x] = guni(uni[x]); }
	
	void init(vector<int> &X, vector<int> &Y) {
		int M = X.size();
		for(int i = 0; i < M; i++) ed.eb(min(X[i], Y[i]), max(X[i], Y[i]));
		sort(all(ed), greater<pii>());
		for(int i = 0; i < N; i++) {
			v[i].push_back(i);
			uni[i] = i;
		}
		//for(auto a : ed) printf("(%d, %d)", a.fi, a.se);
		//puts("");

		for(auto a : ed) {
			int x = guni(a.fi), y = guni(a.se);
			//printf("x = %d, y = %d\n", x, y);
			if(x == y) continue;
			if(v[x].size() < v[y].size()) swap(x, y);
			v[x].insert(v[x].end(), all(v[y]));
			e[x].push_back(a.fi);
			e[x].insert(e[x].end(), all(e[y]));
			uni[y] = x;
		}
		int z = guni(0);
		for(int i = 0; i < N; i++) dn[v[z][i]] = i;
		/*
		for(auto a : v[z]) printf("%d ", a);
		puts("");
		for(auto a : e[z]) printf("%d ", a);
		puts("");
		for(int i = 0; i < N; i++) printf("%d ", dn[i]);
		puts("");
		*/
		seg.init(e[z]);
		for(int i = 0; i < (N - 1) / 2; i++) swap(e[z][i], e[z][N - i - 2]);
		segr.init(e[z]);
	}

	int glb(int x, int L) { return seg.gseg(1, 0, N - 2, dn[x] - 1, L) + 1; }
	int grb(int x, int L) { return N - 2 - segr.gseg(1, 0, N - 2, N - dn[x] - 2, L); }
} hm, ww;

int dot[MAXN];
vector<int> qry[MAXN];
int u[MAXN], d[MAXN];
int bit[MAXN];

void updbit(int x) { for(x += 5; x < MAXN; x += rb(x)) bit[x]++; }
int gbit(int x) {
	int ans = 0;
	for(x += 5; x; x -= rb(x)) ans += bit[x];
	return ans;
}
int gbit(int x, int y) { return gbit(y) - gbit(x - 1); }

vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	N = NN;
	int M = X.size(), Q = S.size();
	hm.init(X, Y);
	for(int i = 0; i < M; i++) {
		X[i] = N - 1 - X[i];
		Y[i] = N - 1 - Y[i];
	}
	ww.init(X, Y);

	for(int i = 0; i < N; i++) dot[hm.dn[i]] = ww.dn[N - i - 1];
	//for(int i = 0; i < Q; i++)
		//printf("%d %d %d %d\n", hm.glb(S[i], L[i]), hm.grb(S[i], L[i]), ww.glb(N - E[i] - 1, N - R[i] - 1), ww.grb(N - E[i] - 1, N - R[i] - 1));
	for(int i = 0; i < Q; i++) {
		int t = hm.glb(S[i], L[i]);
		if(t > 0) qry[t - 1].push_back(-i - 1);
		qry[hm.grb(S[i], L[i])].push_back(i);
		d[i] = ww.glb(N - E[i] - 1, N - R[i] - 1);
		u[i] = ww.grb(N - E[i] - 1, N - R[i] - 1);
	}

	vector<int> ans(Q, 0);
	for(int i = 0; i < N; i++) {
		updbit(dot[i]);
		for(auto a : qry[i]) {
			//printf("i = %d, a = %d\n", i, a);
			if(a >= 0) ans[a] += gbit(d[a], u[a]);
			else ans[-a - 1] -= gbit(d[-a - 1], u[-a - 1]);
		}
	}
	for(auto &a : ans) a = min(a, 1);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23932 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23932 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 30 ms 24688 KB Output is correct
11 Correct 30 ms 24696 KB Output is correct
12 Correct 31 ms 24824 KB Output is correct
13 Correct 31 ms 24696 KB Output is correct
14 Correct 31 ms 24952 KB Output is correct
15 Correct 32 ms 24860 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 93016 KB Output is correct
2 Correct 542 ms 73420 KB Output is correct
3 Correct 576 ms 78948 KB Output is correct
4 Correct 667 ms 84584 KB Output is correct
5 Correct 658 ms 86004 KB Output is correct
6 Correct 807 ms 89452 KB Output is correct
7 Correct 753 ms 94620 KB Output is correct
8 Correct 540 ms 75552 KB Output is correct
9 Correct 489 ms 78832 KB Output is correct
10 Correct 559 ms 83844 KB Output is correct
11 Correct 588 ms 84504 KB Output is correct
12 Correct 610 ms 88296 KB Output is correct
13 Correct 576 ms 74472 KB Output is correct
14 Correct 616 ms 74508 KB Output is correct
15 Correct 628 ms 74208 KB Output is correct
16 Correct 572 ms 74556 KB Output is correct
17 Correct 717 ms 94320 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23932 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 23 ms 23928 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 30 ms 24688 KB Output is correct
11 Correct 30 ms 24696 KB Output is correct
12 Correct 31 ms 24824 KB Output is correct
13 Correct 31 ms 24696 KB Output is correct
14 Correct 31 ms 24952 KB Output is correct
15 Correct 32 ms 24860 KB Output is correct
16 Correct 881 ms 93016 KB Output is correct
17 Correct 542 ms 73420 KB Output is correct
18 Correct 576 ms 78948 KB Output is correct
19 Correct 667 ms 84584 KB Output is correct
20 Correct 658 ms 86004 KB Output is correct
21 Correct 807 ms 89452 KB Output is correct
22 Correct 753 ms 94620 KB Output is correct
23 Correct 540 ms 75552 KB Output is correct
24 Correct 489 ms 78832 KB Output is correct
25 Correct 559 ms 83844 KB Output is correct
26 Correct 588 ms 84504 KB Output is correct
27 Correct 610 ms 88296 KB Output is correct
28 Correct 576 ms 74472 KB Output is correct
29 Correct 616 ms 74508 KB Output is correct
30 Correct 628 ms 74208 KB Output is correct
31 Correct 572 ms 74556 KB Output is correct
32 Correct 717 ms 94320 KB Output is correct
33 Correct 787 ms 88492 KB Output is correct
34 Correct 472 ms 58112 KB Output is correct
35 Correct 716 ms 84916 KB Output is correct
36 Correct 817 ms 89660 KB Output is correct
37 Correct 741 ms 85220 KB Output is correct
38 Correct 818 ms 88424 KB Output is correct
39 Correct 738 ms 86900 KB Output is correct
40 Correct 678 ms 92768 KB Output is correct
41 Correct 611 ms 83688 KB Output is correct
42 Correct 587 ms 87012 KB Output is correct
43 Correct 676 ms 86816 KB Output is correct
44 Correct 676 ms 83728 KB Output is correct
45 Correct 546 ms 82668 KB Output is correct
46 Correct 548 ms 83944 KB Output is correct
47 Correct 578 ms 81144 KB Output is correct
48 Correct 569 ms 80872 KB Output is correct
49 Correct 568 ms 80872 KB Output is correct
50 Correct 563 ms 80744 KB Output is correct
51 Correct 653 ms 91616 KB Output is correct
52 Correct 649 ms 92512 KB Output is correct