oj.uz

Submission #138721

# Submission time Handle Problem Language Result Execution time Memory
138721 2019-07-30T09:10:22 Z MAMBA Werewolf (IOI18_werewolf) C++17
100 / 100
 2458 ms 253380 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j ,k) for (int i = j; i < (int)k; i++)
#define pb push_back

typedef vector<int> vi;

const int N = 2e5 + 10;

struct dsu {
	int par[N];
	vi h[N];
	unordered_map<int , int> mp[N];
	dsu() {
		iota(par , par + N, 0);
		rep(i , 0 , N) { 
			mp[i][i] = 0;
			h[i].pb(i);
		}
	}
	int getPar(int v) {
		return par[v] == v ? v : par[v] = getPar(par[v]);
	}
	bool merge(int u , int v) {
		if ((v = getPar(v)) == (u = getPar(u))) return false;
		if (h[u].size() < h[v].size()) swap(u , v);
		for (auto e : h[v]) {
			mp[u][e] = h[u].size();
			h[u].pb(e);
		}
		par[v] = u;
		return true;
	}		
} dsL , dsR;

int LV[N], RV[N], LS[N] , RS[N];
vi adj[N], lid[N] , rid[N];
map<pair<int , int> , vi> mp1 , mp2;

inline bool Eshterak(int v, int vs , int u , int us) {


	if (us < vs) {
		vi &vec = mp1[{v , u}];
		while ((int)vec.size() < us) {
			int tmp = dsR.h[u][vec.size()];
			int me;
			if (dsL.mp[v].count(tmp))
				me = dsL.mp[v][tmp];
			else 
				me = 1e9;
			if (vec.size()) me = min(me , vec.back());
			vec.pb(me);
		}
		return vec[us - 1] < vs;
	}
	else {
		vi &vec = mp2[{v , u}];
		while ((int)vec.size() < vs) {
			int tmp = dsL.h[v][vec.size()];
			int me;
			if (dsR.mp[u].count(tmp))
				me = dsR.mp[u][tmp];
			else 
				me = 1e9;
			if (vec.size()) me = min(me , vec.back());
			vec.pb(me);
		}

		return vec[vs - 1] < us;
	}
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	int m = X.size();
	rep(i , 0 , m) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}
	int q = S.size();
	rep(i , 0 , q) {
		lid[L[i]].pb(i);
		rid[R[i]].pb(i);
	}

	{
		for (int i = N - 1; ~i; i--) {
			for (auto e : adj[i])
				if (e >= i)
					dsL.merge(i , e);
			for (auto e : lid[i]) {
				int u = dsL.getPar(S[e]);
				LV[e] = u;
				LS[e] = dsL.h[u].size();

			}
		}
	}
	{
		for (int i = 0 ; i < N; i++) {
			for (auto e : adj[i])
				if (e <= i)
					dsR.merge(i , e);
			for (auto e : rid[i]) {
				int u = dsR.getPar(E[e]);
				RV[e] = u;
				RS[e] = dsR.h[u].size();

			}
		}
	}


	vi res(q);

	rep(i , 0 , q) 
		if (Eshterak(LV[i] , LS[i] , RV[i] , RS[i]))
			res[i] = 1;

	return res;

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 84860 KB Output is correct
2 Correct 154 ms 84856 KB Output is correct
3 Correct 155 ms 84864 KB Output is correct
4 Correct 155 ms 84856 KB Output is correct
5 Correct 164 ms 84984 KB Output is correct
6 Correct 168 ms 85024 KB Output is correct
7 Correct 156 ms 84944 KB Output is correct
8 Correct 156 ms 84956 KB Output is correct
9 Correct 157 ms 85004 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 84860 KB Output is correct
2 Correct 154 ms 84856 KB Output is correct
3 Correct 155 ms 84864 KB Output is correct
4 Correct 155 ms 84856 KB Output is correct
5 Correct 164 ms 84984 KB Output is correct
6 Correct 168 ms 85024 KB Output is correct
7 Correct 156 ms 84944 KB Output is correct
8 Correct 156 ms 84956 KB Output is correct
9 Correct 157 ms 85004 KB Output is correct
10 Correct 164 ms 86008 KB Output is correct
11 Correct 164 ms 86264 KB Output is correct
12 Correct 170 ms 87032 KB Output is correct
13 Correct 163 ms 85936 KB Output is correct
14 Correct 164 ms 86228 KB Output is correct
15 Correct 164 ms 86216 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2458 ms 253380 KB Output is correct
2 Correct 983 ms 147120 KB Output is correct
3 Correct 1040 ms 169180 KB Output is correct
4 Correct 1611 ms 198440 KB Output is correct
5 Correct 1479 ms 204864 KB Output is correct
6 Correct 1998 ms 226208 KB Output is correct
7 Correct 2062 ms 245976 KB Output is correct
8 Correct 859 ms 152000 KB Output is correct
9 Correct 913 ms 168108 KB Output is correct
10 Correct 1172 ms 191624 KB Output is correct
11 Correct 1304 ms 197968 KB Output is correct
12 Correct 1519 ms 209940 KB Output is correct
13 Correct 865 ms 146356 KB Output is correct
14 Correct 881 ms 146208 KB Output is correct
15 Correct 894 ms 146360 KB Output is correct
16 Correct 891 ms 146304 KB Output is correct
17 Correct 1956 ms 239852 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 84860 KB Output is correct
2 Correct 154 ms 84856 KB Output is correct
3 Correct 155 ms 84864 KB Output is correct
4 Correct 155 ms 84856 KB Output is correct
5 Correct 164 ms 84984 KB Output is correct
6 Correct 168 ms 85024 KB Output is correct
7 Correct 156 ms 84944 KB Output is correct
8 Correct 156 ms 84956 KB Output is correct
9 Correct 157 ms 85004 KB Output is correct
10 Correct 164 ms 86008 KB Output is correct
11 Correct 164 ms 86264 KB Output is correct
12 Correct 170 ms 87032 KB Output is correct
13 Correct 163 ms 85936 KB Output is correct
14 Correct 164 ms 86228 KB Output is correct
15 Correct 164 ms 86216 KB Output is correct
16 Correct 2458 ms 253380 KB Output is correct
17 Correct 983 ms 147120 KB Output is correct
18 Correct 1040 ms 169180 KB Output is correct
19 Correct 1611 ms 198440 KB Output is correct
20 Correct 1479 ms 204864 KB Output is correct
21 Correct 1998 ms 226208 KB Output is correct
22 Correct 2062 ms 245976 KB Output is correct
23 Correct 859 ms 152000 KB Output is correct
24 Correct 913 ms 168108 KB Output is correct
25 Correct 1172 ms 191624 KB Output is correct
26 Correct 1304 ms 197968 KB Output is correct
27 Correct 1519 ms 209940 KB Output is correct
28 Correct 865 ms 146356 KB Output is correct
29 Correct 881 ms 146208 KB Output is correct
30 Correct 894 ms 146360 KB Output is correct
31 Correct 891 ms 146304 KB Output is correct
32 Correct 1956 ms 239852 KB Output is correct
33 Correct 2178 ms 198860 KB Output is correct
34 Correct 492 ms 114808 KB Output is correct
35 Correct 1261 ms 160600 KB Output is correct
36 Correct 2037 ms 197164 KB Output is correct
37 Correct 1415 ms 164096 KB Output is correct
38 Correct 1989 ms 186372 KB Output is correct
39 Correct 1387 ms 169104 KB Output is correct
40 Correct 1185 ms 160828 KB Output is correct
41 Correct 1124 ms 156528 KB Output is correct
42 Correct 1318 ms 174376 KB Output is correct
43 Correct 1201 ms 151452 KB Output is correct
44 Correct 1299 ms 157384 KB Output is correct
45 Correct 971 ms 151844 KB Output is correct
46 Correct 1084 ms 161360 KB Output is correct
47 Correct 891 ms 147088 KB Output is correct
48 Correct 844 ms 147512 KB Output is correct
49 Correct 866 ms 147284 KB Output is correct
50 Correct 871 ms 147640 KB Output is correct
51 Correct 1191 ms 158104 KB Output is correct
52 Correct 1248 ms 158028 KB Output is correct