oj.uz

Submission #77921

# Submission time Handle Problem Language Result Execution time Memory
77921 2018-10-01T07:54:28 Z Just_Solve_The_Problem Werewolf (IOI18_werewolf) C++11
49 / 100
 4000 ms 95572 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
// #include "grader.cpp"

#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define okk puts("OK");

using namespace std;

const int smallN = (int)6e3 + 7;
const int N = (int)2e5 + 7;

int was[smallN];
int used[smallN];
vector < int > gr[N];
int l, r;
int n;
       
void dfs1(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to >= l) dfs1(to, v);
	}
}

void dfs2(int v, int pr) {
	was[v]++;
	used[v] = 1;
	for (int to : gr[v]) {
		if (!used[to] && to <= r) dfs2(to, v);
	}
}  

vector < int > subtask12(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	for (int i = 0; i < (int)X.size(); i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	vector < int > ans;
	int q = S.size();
	for (int i = 0; i < q; i++) {
		l = L[i];
		r = R[i];
		memset(was, 0, sizeof was);
		dfs1(S[i], S[i]);
		memset(used, 0, sizeof used);
		dfs2(E[i], E[i]);
		memset(used, 0, sizeof used);
		int ok = 1;
		for (int j = l; j <= r; j++) {
			if (was[j] == 2) {
				ans.pb(1);
				ok = 0;
				break;
			}
		}
		if (ok) {
			ans.pb(0);
		}
	}
	return ans;
}

struct sparse {
	int table[2][20][N];
	/*
	0 = min
	1 = max
 	*/
 	sparse() { 		
 	}
	int numlog[N];
	void build(vector < int > &a) {
		numlog[0] = numlog[1] = 0;
		int nn = a.size();
		for (int i = 2; i < N; i++) {
			numlog[i] = numlog[i / 2] + 1;
		}
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < nn; j++) {
				if (i == 0) {
					table[0][i][j] = table[1][i][j] = a[j];
				} else {
					table[0][i][j] = min(table[0][i - 1][j], table[0][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
					table[1][i][j] = max(table[1][i - 1][j], table[1][i - 1][min(j + (1 << (i - 1)), nn - 1)]);
				}
			}
		}
	}
	int getmax(int l, int r) {
		int lg = numlog[r - l + 1];
		return max(table[1][lg][l], table[1][lg][r - (1 << lg) + 1]);
	}
	int getmin(int l, int r) {
		int lg = numlog[r - l + 1];
		return min(table[0][lg][l], table[0][lg][r - (1 << lg) + 1]);
	}
};

vector < int > ar;
vector < int > pos;
sparse tb;

void dfs3(int v, int pr, int h = 0) {
	ar[h] = v;
	for (int to : gr[v]) {
		if (to != pr) {
			dfs3(to, v, h + 1);
		}
	}
}

pii getrange1(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(max(0, v - md + 1), v) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmin(v, min(v + md - 1, n - 1)) >= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}

pii getrange2(int v, int lim) {
	pii ret;
	ret = mk(v, v);
	int lo, hi;
	lo = 1; 
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(max(0, v - md + 1), v) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.fr = max(0, v - lo + 1);
	lo = 1;
	hi = n + 1;
	while (hi - lo > 1) {
		int md = (lo + hi) >> 1;
		if (tb.getmax(v, min(v + md - 1, n - 1)) <= lim) {
			lo = md;
		} else {
			hi = md;
		}
	}
	ret.sc = min(v + lo - 1, n - 1);
	return ret;
}

vector < int > subtask3(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();
	ar.resize(n);
	pos.resize(n);
	vector < int > ans;
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}
	for (int i = 0; i < n; i++) {
		if ((int)gr[i].size() == 1) {
			dfs3(i, i);
			break;
		}
	}         
	tb.build(ar);
	for (int i = 0; i < n; i++) {
		pos[ar[i]] = i;
	}
	int q = (int)S.size();
	ans.resize(q);
	for (int i = 0; i < q; i++) {
		int &res = ans[i];
		res = 0;
		pair < int, int > asd1 = getrange1(pos[S[i]], L[i]);
		pair < int, int > asd2 = getrange2(pos[E[i]], R[i]);
		if ((pos[S[i]] <= pos[E[i]] && asd1.sc >= asd2.fr) || (pos[E[i]] <= pos[S[i]] && asd2.sc >= asd1.fr)) {
			res = 1;
		}
	}  
	return ans;
}

struct DSU {
	int par[N];
	DSU() {
		iota(par, par + N, 0);
	}
	int getpar(int x) {
		return ((par[x] == x) ? x : getpar(par[x]));
	}
};
DSU dsu1, dsu2;

struct query {
	int id, t, x;
	query() {
	}
	query(int _id, int _t, int _x) {
		id = _id;
		t = _t;
		x = _x;
	}
};
vector < query > qq;

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos) {
		while (pos < N) {
			tree[pos]++;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
};
fen tr;

vector < vector < int > > gr1, gr2;
int par[2][20][N];
int tiktak;
int tin[2][N], tout[2][N];
int pos1[N]; 

void dfs(vector < vector < int > > &GR, int id, int v, int pr) {
	par[id][0][v] = pr;
	for (int i = 1; i < 20; i++) {
		par[id][i][v] = par[id][i - 1][par[id][i - 1][v]];
	}
	tin[id][v] = ++tiktak;
	for (int to : GR[v]) {
		dfs(GR, id, to, v);
	}
	tout[id][v] = tiktak;
}

vector < int > subtask4(int &N, vector < int > &X, vector < int > &Y, vector < int > &S, vector < int > &E, vector < int > &L, vector < int > &R) {
	n = N;
	dsu1 = DSU();
	dsu2 = DSU();
	int m = X.size();
	int q = S.size();
	vector < int > ans;
	gr1.resize(n);
	gr2.resize(n);
	ans.resize(q);
	for (int i = 0; i < m; i++) {
		gr[X[i]].pb(Y[i]);
		gr[Y[i]].pb(X[i]);
	}                      
	for (int i = n - 1; i >= 0; i--) {
		for (int to : gr[i]) {
			if (i > to) continue;
			int x = dsu1.getpar(i);
			int y = dsu1.getpar(to);
			if (x == y) continue;
			dsu1.par[y] = x;
			gr1[x].pb(y);
		}
	}                       
	for (int i = 0; i < n; i++) {
		for (int to : gr[i]) {
			if (i < to) continue;
			int x = dsu2.getpar(i);
			int y = dsu2.getpar(to);
			if (x == y) continue;
			dsu2.par[y] = x;
			gr2[x].pb(y);
		}
	}                           
	dfs(gr1, 0, dsu1.getpar(0), dsu1.getpar(0));
	tiktak = 0;
	dfs(gr2, 1, dsu2.getpar(0), dsu2.getpar(0));
	for (int i = 0; i < q; i++) {
		int x = S[i];
		int y = E[i];
		int l = L[i];
		int r = R[i];               
		for (int j = 19; j >= 0; j--) { 
			if (par[0][j][x] >= l) x = par[0][j][x];
			if (par[1][j][y] <= r) y = par[1][j][y];
		}
		// cout << i << ' ' << x << ' ' << y << endl;
		qq.pb(query(~i, tin[0][x] - 1, y));
		qq.pb(query(i, tout[0][x], y));
	}
	sort(qq.begin(), qq.end(), [&](query &a, query &b) {
		return a.t < b.t;
	});
	// puts("***");
	for (int i = 0; i < n; i++) {
		pos1[tin[0][i] - 1] = tin[1][i];
	}
	int ord = 0;
	q = (int)qq.size();
	/*for (auto to : qq) {
		cout << to.id << ' ' << to.t << ' ' << to.x << '\n';
	} */
	for (int i = 0; i < q; i++) {
		while (ord < qq[i].t) tr.upd(pos1[ord++]);
		int delta = tr.get(tout[1][qq[i].x]) - tr.get(tin[1][qq[i].x] - 1);
		if (qq[i].id < 0) {
			ans[~qq[i].id] -= delta;
		} else {
			ans[qq[i].id] += delta;
		}
	}
	for (int i = 0; i < (int)ans.size(); i++) {
		ans[i] = (ans[i] > 0);
	}
	return ans;                     
}


vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R) {
	return subtask4(N, X, Y, S, E, L, R);
	if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000) {
		return subtask12(N, X, Y, S, E, L, R);
	} else if ((int)X.size() == N - 1) {
		return subtask3(N, X, Y, S, E, L, R);
	} 
	return subtask4(N, X, Y, S, E, L, R);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8440 KB Output is correct
2 Correct 9 ms 8572 KB Output is correct
3 Correct 9 ms 8572 KB Output is correct
4 Correct 9 ms 8572 KB Output is correct
5 Correct 9 ms 8572 KB Output is correct
6 Correct 8 ms 8620 KB Output is correct
7 Correct 9 ms 8620 KB Output is correct
8 Correct 9 ms 8628 KB Output is correct
9 Correct 9 ms 8656 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8440 KB Output is correct
2 Correct 9 ms 8572 KB Output is correct
3 Correct 9 ms 8572 KB Output is correct
4 Correct 9 ms 8572 KB Output is correct
5 Correct 9 ms 8572 KB Output is correct
6 Correct 8 ms 8620 KB Output is correct
7 Correct 9 ms 8620 KB Output is correct
8 Correct 9 ms 8628 KB Output is correct
9 Correct 9 ms 8656 KB Output is correct
10 Correct 18 ms 9936 KB Output is correct
11 Correct 16 ms 9940 KB Output is correct
12 Correct 16 ms 9940 KB Output is correct
13 Correct 23 ms 10096 KB Output is correct
14 Correct 22 ms 10128 KB Output is correct
15 Correct 22 ms 10128 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 83480 KB Output is correct
2 Correct 803 ms 89456 KB Output is correct
3 Correct 846 ms 89456 KB Output is correct
4 Correct 838 ms 89456 KB Output is correct
5 Correct 934 ms 89456 KB Output is correct
6 Correct 1018 ms 89456 KB Output is correct
7 Correct 1045 ms 89456 KB Output is correct
8 Correct 843 ms 89456 KB Output is correct
9 Correct 657 ms 89456 KB Output is correct
10 Correct 592 ms 89456 KB Output is correct
11 Correct 627 ms 89456 KB Output is correct
12 Correct 578 ms 89456 KB Output is correct
13 Correct 897 ms 95572 KB Output is correct
14 Correct 1024 ms 95572 KB Output is correct
15 Correct 826 ms 95572 KB Output is correct
16 Correct 840 ms 95572 KB Output is correct
17 Correct 972 ms 95572 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8440 KB Output is correct
2 Correct 9 ms 8572 KB Output is correct
3 Correct 9 ms 8572 KB Output is correct
4 Correct 9 ms 8572 KB Output is correct
5 Correct 9 ms 8572 KB Output is correct
6 Correct 8 ms 8620 KB Output is correct
7 Correct 9 ms 8620 KB Output is correct
8 Correct 9 ms 8628 KB Output is correct
9 Correct 9 ms 8656 KB Output is correct
10 Correct 18 ms 9936 KB Output is correct
11 Correct 16 ms 9940 KB Output is correct
12 Correct 16 ms 9940 KB Output is correct
13 Correct 23 ms 10096 KB Output is correct
14 Correct 22 ms 10128 KB Output is correct
15 Correct 22 ms 10128 KB Output is correct
16 Correct 1097 ms 83480 KB Output is correct
17 Correct 803 ms 89456 KB Output is correct
18 Correct 846 ms 89456 KB Output is correct
19 Correct 838 ms 89456 KB Output is correct
20 Correct 934 ms 89456 KB Output is correct
21 Correct 1018 ms 89456 KB Output is correct
22 Correct 1045 ms 89456 KB Output is correct
23 Correct 843 ms 89456 KB Output is correct
24 Correct 657 ms 89456 KB Output is correct
25 Correct 592 ms 89456 KB Output is correct
26 Correct 627 ms 89456 KB Output is correct
27 Correct 578 ms 89456 KB Output is correct
28 Correct 897 ms 95572 KB Output is correct
29 Correct 1024 ms 95572 KB Output is correct
30 Correct 826 ms 95572 KB Output is correct
31 Correct 840 ms 95572 KB Output is correct
32 Correct 972 ms 95572 KB Output is correct
33 Correct 1588 ms 95572 KB Output is correct
34 Correct 1447 ms 95572 KB Output is correct
35 Execution timed out 4050 ms 95572 KB Time limit exceeded
36 Halted 0 ms 0 KB -