oj.uz

Submission #77923

# Submission time Handle Problem Language Result Execution time Memory
77923 2018-10-01T07:56:50 Z Just_Solve_The_Problem Werewolf (IOI18_werewolf) C++11
49 / 100
 4000 ms 95700 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 10 ms 8412 KB Output is correct
2 Correct 10 ms 8472 KB Output is correct
3 Correct 9 ms 8532 KB Output is correct
4 Correct 11 ms 8532 KB Output is correct
5 Correct 9 ms 8532 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 9 ms 8660 KB Output is correct
8 Correct 9 ms 8660 KB Output is correct
9 Correct 9 ms 8660 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8412 KB Output is correct
2 Correct 10 ms 8472 KB Output is correct
3 Correct 9 ms 8532 KB Output is correct
4 Correct 11 ms 8532 KB Output is correct
5 Correct 9 ms 8532 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 9 ms 8660 KB Output is correct
8 Correct 9 ms 8660 KB Output is correct
9 Correct 9 ms 8660 KB Output is correct
10 Correct 17 ms 9876 KB Output is correct
11 Correct 17 ms 9936 KB Output is correct
12 Correct 18 ms 9936 KB Output is correct
13 Correct 23 ms 10124 KB Output is correct
14 Correct 22 ms 10156 KB Output is correct
15 Correct 25 ms 10156 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 83596 KB Output is correct
2 Correct 941 ms 89228 KB Output is correct
3 Correct 861 ms 89228 KB Output is correct
4 Correct 939 ms 89228 KB Output is correct
5 Correct 967 ms 89228 KB Output is correct
6 Correct 1171 ms 89228 KB Output is correct
7 Correct 1167 ms 89228 KB Output is correct
8 Correct 855 ms 89272 KB Output is correct
9 Correct 599 ms 89272 KB Output is correct
10 Correct 535 ms 89272 KB Output is correct
11 Correct 594 ms 89272 KB Output is correct
12 Correct 631 ms 89272 KB Output is correct
13 Correct 808 ms 95496 KB Output is correct
14 Correct 789 ms 95512 KB Output is correct
15 Correct 928 ms 95516 KB Output is correct
16 Correct 924 ms 95700 KB Output is correct
17 Correct 1144 ms 95700 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8412 KB Output is correct
2 Correct 10 ms 8472 KB Output is correct
3 Correct 9 ms 8532 KB Output is correct
4 Correct 11 ms 8532 KB Output is correct
5 Correct 9 ms 8532 KB Output is correct
6 Correct 9 ms 8660 KB Output is correct
7 Correct 9 ms 8660 KB Output is correct
8 Correct 9 ms 8660 KB Output is correct
9 Correct 9 ms 8660 KB Output is correct
10 Correct 17 ms 9876 KB Output is correct
11 Correct 17 ms 9936 KB Output is correct
12 Correct 18 ms 9936 KB Output is correct
13 Correct 23 ms 10124 KB Output is correct
14 Correct 22 ms 10156 KB Output is correct
15 Correct 25 ms 10156 KB Output is correct
16 Correct 1103 ms 83596 KB Output is correct
17 Correct 941 ms 89228 KB Output is correct
18 Correct 861 ms 89228 KB Output is correct
19 Correct 939 ms 89228 KB Output is correct
20 Correct 967 ms 89228 KB Output is correct
21 Correct 1171 ms 89228 KB Output is correct
22 Correct 1167 ms 89228 KB Output is correct
23 Correct 855 ms 89272 KB Output is correct
24 Correct 599 ms 89272 KB Output is correct
25 Correct 535 ms 89272 KB Output is correct
26 Correct 594 ms 89272 KB Output is correct
27 Correct 631 ms 89272 KB Output is correct
28 Correct 808 ms 95496 KB Output is correct
29 Correct 789 ms 95512 KB Output is correct
30 Correct 928 ms 95516 KB Output is correct
31 Correct 924 ms 95700 KB Output is correct
32 Correct 1144 ms 95700 KB Output is correct
33 Correct 1669 ms 95700 KB Output is correct
34 Correct 1499 ms 95700 KB Output is correct
35 Execution timed out 4062 ms 95700 KB Time limit exceeded
36 Halted 0 ms 0 KB -