oj.uz

답안 #332548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332548 2020-12-02T20:30:20 Z pit4h 늑대인간 (IOI18_werewolf) C++14
15 / 100
 2005 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 Node {
	int l, r, val;
	Node *ls = NULL, *rs = NULL;
	Node(int _l, int _r) {
		l = _l; r = _r; val=0;
	}
	void push() {
		if(!ls) {
			ls = new Node(l, (l+r)/2);
			rs = new Node((l+r)/2+1, r);
		}
	}
};
struct Segtree {
	vector<int> updates;
	Node *root;
	Segtree(int _N) {
		root = new Node(0, _N-1);
	}
	void ins(int x, Node* cur) {
		if(x > (cur->r) || x < (cur->l)) {
			return;
		}
		cur->val++;
		if((cur->l) == (cur->r)) return;
		cur->push();
		ins(x, cur->ls);
		ins(x, cur->rs);
	}
	void upd(int x) {
		updates.push_back(x);
		ins(x, root);
	}
	int qry(int l, int r, Node* cur) {
		if(l > (cur->r) || r < (cur->l)) {
			return 0;
		}
		if(l <= (cur->l) && r >= (cur->r)) {
			return cur->val;
		}
		cur->push();
		return qry(l, r, cur->ls) + qry(l, r, cur->rs);
	}
	void clr() {
		updates.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, occ[x]->root) > 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

# 결과 실행 시간 메모리 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 384 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 14 ms 5484 KB Output is correct
11 Correct 13 ms 5868 KB Output is correct
12 Correct 15 ms 6892 KB Output is correct
13 Correct 14 ms 7148 KB Output is correct
14 Correct 17 ms 9068 KB Output is correct
15 Correct 11 ms 3692 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2005 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

# 결과 실행 시간 메모리 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 384 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 14 ms 5484 KB Output is correct
11 Correct 13 ms 5868 KB Output is correct
12 Correct 15 ms 6892 KB Output is correct
13 Correct 14 ms 7148 KB Output is correct
14 Correct 17 ms 9068 KB Output is correct
15 Correct 11 ms 3692 KB Output is correct
16 Runtime error 2005 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -