oj.uz

Submission #75111

# Submission time Handle Problem Language Result Execution time Memory
75111 2018-09-08T11:36:45 Z Namnamseo Werewolf (IOI18_werewolf) C++17
100 / 100
 2183 ms 169764 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)

#define all(v) (v).begin(), (v).end()
#define x first
#define y second

#define pb push_back
#define eb emplace_back
using pp=pair<int,int>;

const int MAX_N = 200001;
const int MAX_V = 400001;

int n;

vector<int> gp[MAX_N];

struct asdf {
	int par[MAX_N];
	int tnode[MAX_N];

	vector<int> te[MAX_V];
	int tp[20][MAX_V];
	int tt[MAX_V];
	int v;

	void init(){
		iota(par+1, par+n+1, 1);
		iota(tnode+1, tnode+n+1, 1);
		v = n;
	}

	int root(int x){ return (x == par[x]) ? x : (par[x] = root(par[x])); }

	void connect(int x, int y, int tm){
		x = root(x); y = root(y);
		if(x == y) return;
		int a = tnode[x], b = tnode[y];
		tp[0][a] = tp[0][b] = ++v;
		tt[v] = tm;
		te[v].pb(a); te[v].pb(b);
		par[x] = y; tnode[y] = v;
	}

	int nt;
	int tin[MAX_V];
	int tout[MAX_V];

	void dfs(int x){
		tin[x] = nt + 1;
		if(x <= n) ++nt;
		for(int y:te[x]) dfs(y);
		tout[x] = nt;
	}

	void inflate(){
		rrep(i, 19) rrep(j, v) tp[i][j] = tp[i-1][tp[i-1][j]];
		dfs(v);
	}

	pp get_range(int v, int tb){
		for(int i=19; 0<=i; --i){
			int a = tp[i][v];
			if(!a) continue;
			if(tt[a] <= tb) v = a;
		}

		return {tin[v], tout[v]};
	}
} sl, sr;

struct seg2d {
	const static int M = 262144;
	vector<int> yv[M*2];

	void addp(int x, int y){
		for(x+=M; x; x>>=1) yv[x].pb(y);
	}

	void prepare(){
		for(auto& v:yv) sort(all(v));
	}

	inline bool exist(vector<int>& v, int d, int u){
		auto it = lower_bound(all(v), d);
		return (it != v.end()) && (*it <= u);
	}

	inline bool exist(int l, int r, int d, int u){
		for(l+=M, r+=M; l<=r; l>>=1, r>>=1){
			if(l%2==1){ if(exist(yv[l++], d, u)) return 1; }
			if(r%2==0){ if(exist(yv[r--], d, u)) return 1; }
		}
		return 0;
	}
} d2;

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;
	int m = X.size();
	rep(i, m){
		int x=X[i]+1, y=Y[i]+1;
		gp[x].pb(y); gp[y].pb(x);
	}

	sl.init();
	sr.init();

	for(int i=n; 1<=i; --i){
		for(int j:gp[i]) if(i<=j){
			sl.connect(i, j, n-i+1);
		}
	}

	rrep(i, n) for(int j:gp[i]) if(j<=i){
		sr.connect(i, j, i);
	}

	sl.inflate(); sr.inflate();
	rrep(i, n) d2.addp(sr.tin[i], sl.tin[i]);
	d2.prepare();

	int q = L.size();
	vector<int> ans(q);
	rep(i, q){
		pp xr = sr.get_range(E[i]+1, R[i]+1);
		pp yr = sl.get_range(S[i]+1, n-L[i]);
		ans[i] = d2.exist(xr.x, xr.y, yr.x, yr.y);
	}

	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36472 KB Output is correct
2 Correct 37 ms 36596 KB Output is correct
3 Correct 36 ms 36672 KB Output is correct
4 Correct 36 ms 36748 KB Output is correct
5 Correct 40 ms 36748 KB Output is correct
6 Correct 36 ms 36748 KB Output is correct
7 Correct 34 ms 36748 KB Output is correct
8 Correct 38 ms 36748 KB Output is correct
9 Correct 35 ms 36784 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36472 KB Output is correct
2 Correct 37 ms 36596 KB Output is correct
3 Correct 36 ms 36672 KB Output is correct
4 Correct 36 ms 36748 KB Output is correct
5 Correct 40 ms 36748 KB Output is correct
6 Correct 36 ms 36748 KB Output is correct
7 Correct 34 ms 36748 KB Output is correct
8 Correct 38 ms 36748 KB Output is correct
9 Correct 35 ms 36784 KB Output is correct
10 Correct 49 ms 38748 KB Output is correct
11 Correct 50 ms 38768 KB Output is correct
12 Correct 46 ms 38768 KB Output is correct
13 Correct 47 ms 38796 KB Output is correct
14 Correct 49 ms 38796 KB Output is correct
15 Correct 47 ms 38812 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1874 ms 163420 KB Output is correct
2 Correct 1364 ms 166052 KB Output is correct
3 Correct 1342 ms 166052 KB Output is correct
4 Correct 1415 ms 166052 KB Output is correct
5 Correct 1507 ms 166052 KB Output is correct
6 Correct 1727 ms 166052 KB Output is correct
7 Correct 1477 ms 166052 KB Output is correct
8 Correct 1366 ms 166052 KB Output is correct
9 Correct 1206 ms 166052 KB Output is correct
10 Correct 943 ms 166052 KB Output is correct
11 Correct 974 ms 166052 KB Output is correct
12 Correct 1263 ms 166052 KB Output is correct
13 Correct 1513 ms 166152 KB Output is correct
14 Correct 1515 ms 166152 KB Output is correct
15 Correct 1586 ms 166152 KB Output is correct
16 Correct 1511 ms 166192 KB Output is correct
17 Correct 1400 ms 166192 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36472 KB Output is correct
2 Correct 37 ms 36596 KB Output is correct
3 Correct 36 ms 36672 KB Output is correct
4 Correct 36 ms 36748 KB Output is correct
5 Correct 40 ms 36748 KB Output is correct
6 Correct 36 ms 36748 KB Output is correct
7 Correct 34 ms 36748 KB Output is correct
8 Correct 38 ms 36748 KB Output is correct
9 Correct 35 ms 36784 KB Output is correct
10 Correct 49 ms 38748 KB Output is correct
11 Correct 50 ms 38768 KB Output is correct
12 Correct 46 ms 38768 KB Output is correct
13 Correct 47 ms 38796 KB Output is correct
14 Correct 49 ms 38796 KB Output is correct
15 Correct 47 ms 38812 KB Output is correct
16 Correct 1874 ms 163420 KB Output is correct
17 Correct 1364 ms 166052 KB Output is correct
18 Correct 1342 ms 166052 KB Output is correct
19 Correct 1415 ms 166052 KB Output is correct
20 Correct 1507 ms 166052 KB Output is correct
21 Correct 1727 ms 166052 KB Output is correct
22 Correct 1477 ms 166052 KB Output is correct
23 Correct 1366 ms 166052 KB Output is correct
24 Correct 1206 ms 166052 KB Output is correct
25 Correct 943 ms 166052 KB Output is correct
26 Correct 974 ms 166052 KB Output is correct
27 Correct 1263 ms 166052 KB Output is correct
28 Correct 1513 ms 166152 KB Output is correct
29 Correct 1515 ms 166152 KB Output is correct
30 Correct 1586 ms 166152 KB Output is correct
31 Correct 1511 ms 166192 KB Output is correct
32 Correct 1400 ms 166192 KB Output is correct
33 Correct 1964 ms 166192 KB Output is correct
34 Correct 428 ms 166192 KB Output is correct
35 Correct 1945 ms 166192 KB Output is correct
36 Correct 1932 ms 166192 KB Output is correct
37 Correct 2183 ms 166192 KB Output is correct
38 Correct 2102 ms 166192 KB Output is correct
39 Correct 2029 ms 169044 KB Output is correct
40 Correct 1547 ms 169252 KB Output is correct
41 Correct 1559 ms 169252 KB Output is correct
42 Correct 1186 ms 169252 KB Output is correct
43 Correct 1650 ms 169252 KB Output is correct
44 Correct 1765 ms 169252 KB Output is correct
45 Correct 1241 ms 169252 KB Output is correct
46 Correct 1273 ms 169252 KB Output is correct
47 Correct 1591 ms 169252 KB Output is correct
48 Correct 1624 ms 169252 KB Output is correct
49 Correct 1547 ms 169252 KB Output is correct
50 Correct 1581 ms 169252 KB Output is correct
51 Correct 1379 ms 169644 KB Output is correct
52 Correct 1491 ms 169764 KB Output is correct