oj.uz

Submission #76236

# Submission time Handle Problem Language Result Execution time Memory
76236 2018-09-12T12:54:24 Z khsoo01 Werewolf (IOI18_werewolf) C++11
100 / 100
 1290 ms 123464 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef pair<int, int> pii;

const int N = 200005, M = 400005, F = 262144, G = 19, inf = 1e9;

int n, m, q, its[N];

vector<pii> edg;

struct event {
	int p, l, r, v, i;
	bool operator < (const event &T) const {
		return p < T.p;
	}
};

vector<event> swp;

struct disjoint_set {
	int par[2*N];
	void init (int X) {
		for(int i=1;i<=X;i++) {
			par[i] = i;
		}
	}
	int Find (int X) {
		if(par[X] == X) return X;
		return par[X] = Find(par[X]);
	}
	int Union (int X, int Y) {
		X = Find(X);
		Y = Find(Y);
		par[Y] = X;
		return Y;
	}
};

struct connectivity_tree {
	int par[G][2*N], inv[N], ord[N], s[2*N], e[2*N], v[2*N], l[2*N], r[2*N], cc, oc;
	disjoint_set dsj;
	void init (int V) {
		dsj.init(2*n);
		cc = n;
		v[0] = inf;
		for(int i=1;i<=n;i++) {
			v[i] = V;
		}
	}
	void build () {
		for(int i=1;i<G;i++) {
			for(int j=1;j<=cc;j++) {
				par[i][j] = par[i-1][par[i-1][j]];
			}
		}
	}
	void connect (int A, int B, int C) {
		if(dsj.Find(A) == dsj.Find(B)) return;
		++cc;
		int X = dsj.Union(cc, A);
		int Y = dsj.Union(cc, B);
		par[0][X] = cc;
		par[0][Y] = cc;
		l[cc] = X;
		r[cc] = Y;
		v[cc] = C;
	}
	void trav (int I) {
		if(I <= n) {
			oc++;
			s[I] = oc;
			e[I] = oc;
			ord[oc] = I;
			inv[I] = oc;
		}
		else {
			trav(l[I]);
			trav(r[I]);
			s[I] = s[l[I]];
			e[I] = e[r[I]];
		}
	}
	void trav () {trav(cc);}
	pii get (int I, int V) {
		for(int i=G;i--;) {
			if(v[par[i][I]] <= V) I = par[i][I];
		}
		return {s[I], e[I]};
	}
} a, b;

struct segment_tree {
	int v[2*F];
	void upd (int P, int V) {
		P += F;
		while(P) {
			v[P] += V;
			P /= 2;
		}
	}
	int get (int S, int E) {
		S += F;
		E += F;
		int R = 0;
		while(S <= E) {
			if(S%2 == 1) R += v[S++];
			if(E%2 == 0) R += v[E--];
			S /= 2;
			E /= 2;
		}
		return R;
	}
} seg;

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;
	m = (int)_X.size();
	q = (int)_L.size();
	a.init(-n);
	b.init(0);
	for(int i=0;i<m;i++) {
		int A = _X[i]+1, B = _Y[i]+1;
		if(A > B) swap(A, B);
		edg.push_back({A, B});
	}
	sort(edg.begin(), edg.end());
	reverse(edg.begin(), edg.end());
	for(int i=0;i<m;i++) {
		a.connect(edg[i].X, edg[i].Y, -edg[i].X);
	}
	a.build();
	a.trav();
	for(int i=0;i<m;i++) {
		swap(edg[i].X, edg[i].Y);
	}
	sort(edg.begin(), edg.end());
	for(int i=0;i<m;i++) {
		b.connect(edg[i].X, edg[i].Y, edg[i].X);
	}
	b.build();
	b.trav();
	for(int i=0;i<q;i++) {
		int S, E, X, Y;
		tie(S, E) = a.get(_S[i]+1, -_L[i]-1);
		tie(X, Y) = b.get(_E[i]+1, _R[i]+1);
		swp.push_back({E, X, Y, 1, i});
		swp.push_back({S-1, X, Y, -1, i});
	}
	sort(swp.begin(), swp.end());
	int Z = 0;
	for(auto &E : swp) {
		while(Z < E.p) {
			seg.upd(b.inv[a.ord[++Z]], 1);
		}
		its[E.i] += E.v * seg.get(E.l, E.r);
	}
	vector<int> ans;
	for(int i=0;i<q;i++) {
		ans.push_back(its[i] > 0);
	}
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 884 KB Output is correct
3 Correct 3 ms 956 KB Output is correct
4 Correct 3 ms 956 KB Output is correct
5 Correct 2 ms 956 KB Output is correct
6 Correct 3 ms 956 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 884 KB Output is correct
3 Correct 3 ms 956 KB Output is correct
4 Correct 3 ms 956 KB Output is correct
5 Correct 2 ms 956 KB Output is correct
6 Correct 3 ms 956 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 10 ms 2604 KB Output is correct
11 Correct 11 ms 2664 KB Output is correct
12 Correct 10 ms 2664 KB Output is correct
13 Correct 11 ms 2732 KB Output is correct
14 Correct 10 ms 2732 KB Output is correct
15 Correct 11 ms 2792 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 102028 KB Output is correct
2 Correct 1243 ms 103644 KB Output is correct
3 Correct 1196 ms 103644 KB Output is correct
4 Correct 1164 ms 103644 KB Output is correct
5 Correct 1218 ms 103644 KB Output is correct
6 Correct 1165 ms 103644 KB Output is correct
7 Correct 1162 ms 103644 KB Output is correct
8 Correct 1051 ms 103644 KB Output is correct
9 Correct 641 ms 103644 KB Output is correct
10 Correct 477 ms 103644 KB Output is correct
11 Correct 566 ms 103644 KB Output is correct
12 Correct 578 ms 103644 KB Output is correct
13 Correct 1143 ms 103688 KB Output is correct
14 Correct 1134 ms 103880 KB Output is correct
15 Correct 1132 ms 103880 KB Output is correct
16 Correct 1138 ms 103880 KB Output is correct
17 Correct 1026 ms 103880 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 884 KB Output is correct
3 Correct 3 ms 956 KB Output is correct
4 Correct 3 ms 956 KB Output is correct
5 Correct 2 ms 956 KB Output is correct
6 Correct 3 ms 956 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 10 ms 2604 KB Output is correct
11 Correct 11 ms 2664 KB Output is correct
12 Correct 10 ms 2664 KB Output is correct
13 Correct 11 ms 2732 KB Output is correct
14 Correct 10 ms 2732 KB Output is correct
15 Correct 11 ms 2792 KB Output is correct
16 Correct 1242 ms 102028 KB Output is correct
17 Correct 1243 ms 103644 KB Output is correct
18 Correct 1196 ms 103644 KB Output is correct
19 Correct 1164 ms 103644 KB Output is correct
20 Correct 1218 ms 103644 KB Output is correct
21 Correct 1165 ms 103644 KB Output is correct
22 Correct 1162 ms 103644 KB Output is correct
23 Correct 1051 ms 103644 KB Output is correct
24 Correct 641 ms 103644 KB Output is correct
25 Correct 477 ms 103644 KB Output is correct
26 Correct 566 ms 103644 KB Output is correct
27 Correct 578 ms 103644 KB Output is correct
28 Correct 1143 ms 103688 KB Output is correct
29 Correct 1134 ms 103880 KB Output is correct
30 Correct 1132 ms 103880 KB Output is correct
31 Correct 1138 ms 103880 KB Output is correct
32 Correct 1026 ms 103880 KB Output is correct
33 Correct 1276 ms 103880 KB Output is correct
34 Correct 534 ms 103880 KB Output is correct
35 Correct 1290 ms 103948 KB Output is correct
36 Correct 1207 ms 103948 KB Output is correct
37 Correct 1263 ms 103948 KB Output is correct
38 Correct 1280 ms 103948 KB Output is correct
39 Correct 1238 ms 105144 KB Output is correct
40 Correct 1169 ms 108388 KB Output is correct
41 Correct 837 ms 108388 KB Output is correct
42 Correct 518 ms 108388 KB Output is correct
43 Correct 1280 ms 108388 KB Output is correct
44 Correct 1094 ms 108388 KB Output is correct
45 Correct 831 ms 108388 KB Output is correct
46 Correct 802 ms 108388 KB Output is correct
47 Correct 1187 ms 108388 KB Output is correct
48 Correct 1191 ms 112132 KB Output is correct
49 Correct 1107 ms 118632 KB Output is correct
50 Correct 1269 ms 118632 KB Output is correct
51 Correct 961 ms 123344 KB Output is correct
52 Correct 959 ms 123464 KB Output is correct