oj.uz

Submission #332475

# Submission time Handle Problem Language Result Execution time Memory
332475 2020-12-02T16:48:01 Z pit4h Werewolf (IOI18_werewolf) C++14
15 / 100
 1627 ms 524292 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+2, MAXM = 4e5+2, Log = 20;

vector<int> ans;
int Find(int x, vector<int>& f) {
	if(f[x] == x) return x;
	f[x] = Find(f[x], f);
	return f[x];
}
bool Union(int x, int y, vector<int>& f, vector<int>& cnt, vector<int>& mx, bool dir) {
	x = Find(x, f); y = Find(y, f);
	if(x==y) return false;
	if(cnt[x] < cnt[y]) swap(x, y);
	cnt[x] += cnt[y];
	cnt[y] = 0;
	f[y] = x;
	if(!dir) {
		mx[x] = max(mx[x], mx[y]);
	}
	else {
		mx[x] = min(mx[x], mx[y]);
	}
	return true;
}
struct Query {
	int l, r, id;
};
struct Segtree {
	vector<int> updates, tree;
	int base = 1;
	Segtree(int _N) {
		while(base<_N) base*=2;
		tree.resize(2*base+1, 0);
	}
	void upd(int x) {
		updates.push_back(x);
		x += base;
		while(x) {
			tree[x]++;
			x/=2;
		}
	}
	int qry(int l, int r) {
		l+=base; r+=base;
		int res = tree[l]; if(l==r) return res;
		res += tree[r];
		while(l/2 != r/2) {
			if(l%2==0) res += tree[l+1];
			if(r%2==1) res += tree[r-1];
			l /= 2; r /= 2;
		}
		return res;
	}
	void clr() {
		updates.clear();
		tree.clear();
	}
};
Segtree *occ[MAXN];
struct Form {
	vector<vector<int>> g, anc;
	vector<vector<Query>> queries;
	vector<int> pre, range;	
	int N, nr=0;
	Form *other;
	Form(int _N) {
		N = _N;
		g.resize(N); anc.resize(Log, vector<int>(N));
		pre.resize(N); range.resize(N);
		queries.resize(N);
	}
	void build_graph(vector<int>& X, vector<int>& Y, vector<int>& order) {
		int M = X.size();
		vector<int> f(N), cnt(N), mx(N); for(int i=0; i<N; ++i) f[i] = mx[i] = i, cnt[i]=1;
		vector<vector<int>> G(N);
		for(int i=0; i<M; ++i) {
			if( (X[i] < Y[i]) != (order[0] < order.back()) ) {
				swap(X[i], Y[i]);	
			}
			G[Y[i]].push_back(X[i]);
		}
		for(int i: order) {
			for(int j: G[i]) {
				int repj = mx[Find(j, f)];
				if(Union(i, j, f, cnt, mx, (order[0] > order.back()) )) {
					g[i].push_back(repj);
				}
			}
		}		
	}
	void build_anc() {
		for(int j=1; j<Log; ++j) {
			for(int i=0; i<N; ++i) {
				anc[j][i] = anc[j-1][anc[j-1][i]];
			}
		}
	}
	void dfs(int x, int par) {
		anc[0][x] = par;
		pre[x] = nr; nr++;
		range[x] = pre[x];
		for(int i: g[x]) {
			dfs(i, x);
			range[x] = max(range[x], range[i]);
		}		
		if(x==par) {
			build_anc();
		}
	}
	int lowest_ancestor(int x, int h) {
		for(int i=Log-1; i>=0; --i) {
			if(x==h) break;
			if(anc[i][x]==h || (x < h) == (anc[i][x] < h)) {
				x = anc[i][x];
			}
		}
		return x;
	}
	void solve(int x, int p) {
		int big_child = -1;
		for(int i: g[x]) {
			solve(i, x);	
			if(big_child==-1 || occ[i]->updates.size() > occ[big_child]->updates.size()) {
				big_child = i;
			}
		}
		if(big_child==-1) {
			occ[x] = new Segtree(N);
		}
		else {
			occ[x] = occ[big_child];
		}
		for(int i: g[x]) {
			if(i!=big_child) {
				for(int j: occ[i]->updates) {
					occ[x]->upd(j);
				}
				occ[i]->clr();
			}
		}
		occ[x]->upd(other->pre[x]);
		for(auto q: queries[x]) {
			ans[q.id] = (occ[x]->qry(q.l, q.r) > 0);
		}
	}
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
	swap(S, E); // == swap(human, wolf)
	int Q = S.size();
	ans.resize(Q);

	vector<int> order;
	for(int i=0; i<N; ++i) order.push_back(i);

	Form human(N), wolf(N);
	wolf.other = &human;

	human.build_graph(X, Y, order);
	reverse(order.begin(), order.end());
	wolf.build_graph(X, Y, order);


	human.dfs(N-1, N-1);
	wolf.dfs(0, 0);
	
	for(int i=0; i<Q; ++i) {
		S[i] = human.lowest_ancestor(S[i], R[i]);
		E[i] = wolf.lowest_ancestor(E[i], L[i]);
		if(S[i] > R[i] || E[i] < L[i]) continue;
		wolf.queries[E[i]].push_back({human.pre[S[i]], human.range[S[i]], i});
	}
	wolf.solve(0, 0);

	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 32 ms 37996 KB Output is correct
11 Correct 31 ms 39020 KB Output is correct
12 Correct 29 ms 33900 KB Output is correct
13 Correct 38 ms 46828 KB Output is correct
14 Correct 39 ms 50412 KB Output is correct
15 Correct 22 ms 22764 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1627 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 32 ms 37996 KB Output is correct
11 Correct 31 ms 39020 KB Output is correct
12 Correct 29 ms 33900 KB Output is correct
13 Correct 38 ms 46828 KB Output is correct
14 Correct 39 ms 50412 KB Output is correct
15 Correct 22 ms 22764 KB Output is correct
16 Runtime error 1627 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -