oj.uz

Submission #77925

# Submission time Handle Problem Language Result Execution time Memory
77925 2018-10-01T07:59:17 Z Just_Solve_The_Problem Werewolf (IOI18_werewolf) C++11
49 / 100
 4000 ms 95640 KB 
#include <vector>
#include <memory.h>
#include <algorithm>
#include <numeric>
#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 8620 KB Output is correct
3 Correct 9 ms 8620 KB Output is correct
4 Correct 9 ms 8620 KB Output is correct
5 Correct 9 ms 8648 KB Output is correct
6 Correct 11 ms 8648 KB Output is correct
7 Correct 9 ms 8648 KB Output is correct
8 Correct 9 ms 8648 KB Output is correct
9 Correct 9 ms 8648 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 8620 KB Output is correct
3 Correct 9 ms 8620 KB Output is correct
4 Correct 9 ms 8620 KB Output is correct
5 Correct 9 ms 8648 KB Output is correct
6 Correct 11 ms 8648 KB Output is correct
7 Correct 9 ms 8648 KB Output is correct
8 Correct 9 ms 8648 KB Output is correct
9 Correct 9 ms 8648 KB Output is correct
10 Correct 20 ms 9912 KB Output is correct
11 Correct 26 ms 9912 KB Output is correct
12 Correct 16 ms 9912 KB Output is correct
13 Correct 23 ms 10112 KB Output is correct
14 Correct 30 ms 10112 KB Output is correct
15 Correct 23 ms 10112 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1194 ms 83440 KB Output is correct
2 Correct 972 ms 89292 KB Output is correct
3 Correct 920 ms 89292 KB Output is correct
4 Correct 1051 ms 89292 KB Output is correct
5 Correct 858 ms 89292 KB Output is correct
6 Correct 1024 ms 89292 KB Output is correct
7 Correct 1055 ms 89292 KB Output is correct
8 Correct 680 ms 89292 KB Output is correct
9 Correct 596 ms 89292 KB Output is correct
10 Correct 525 ms 89292 KB Output is correct
11 Correct 592 ms 89292 KB Output is correct
12 Correct 594 ms 89292 KB Output is correct
13 Correct 870 ms 95504 KB Output is correct
14 Correct 918 ms 95640 KB Output is correct
15 Correct 889 ms 95640 KB Output is correct
16 Correct 942 ms 95640 KB Output is correct
17 Correct 1183 ms 95640 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 8620 KB Output is correct
3 Correct 9 ms 8620 KB Output is correct
4 Correct 9 ms 8620 KB Output is correct
5 Correct 9 ms 8648 KB Output is correct
6 Correct 11 ms 8648 KB Output is correct
7 Correct 9 ms 8648 KB Output is correct
8 Correct 9 ms 8648 KB Output is correct
9 Correct 9 ms 8648 KB Output is correct
10 Correct 20 ms 9912 KB Output is correct
11 Correct 26 ms 9912 KB Output is correct
12 Correct 16 ms 9912 KB Output is correct
13 Correct 23 ms 10112 KB Output is correct
14 Correct 30 ms 10112 KB Output is correct
15 Correct 23 ms 10112 KB Output is correct
16 Correct 1194 ms 83440 KB Output is correct
17 Correct 972 ms 89292 KB Output is correct
18 Correct 920 ms 89292 KB Output is correct
19 Correct 1051 ms 89292 KB Output is correct
20 Correct 858 ms 89292 KB Output is correct
21 Correct 1024 ms 89292 KB Output is correct
22 Correct 1055 ms 89292 KB Output is correct
23 Correct 680 ms 89292 KB Output is correct
24 Correct 596 ms 89292 KB Output is correct
25 Correct 525 ms 89292 KB Output is correct
26 Correct 592 ms 89292 KB Output is correct
27 Correct 594 ms 89292 KB Output is correct
28 Correct 870 ms 95504 KB Output is correct
29 Correct 918 ms 95640 KB Output is correct
30 Correct 889 ms 95640 KB Output is correct
31 Correct 942 ms 95640 KB Output is correct
32 Correct 1183 ms 95640 KB Output is correct
33 Correct 1568 ms 95640 KB Output is correct
34 Correct 1447 ms 95640 KB Output is correct
35 Execution timed out 4013 ms 95640 KB Time limit exceeded
36 Halted 0 ms 0 KB -