Submission #741853

#	Time	Username	Problem	Language	Result	Execution time	Memory
741853		Abrar_Al_Samit	Werewolf (IOI18_werewolf)	C++17	100 / 100	633 ms	119700 KiB

werewolf

#include<bits/stdc++.h>

#include "werewolf.h"
using namespace std;

const int nax = 2e5 + 10;
int rep1[nax], rep2[nax];
pair<int,int> x_co[nax * 2], y_co[nax * 2];
int tt;
int cnt[nax];

struct DSU {
	int par[nax], sz[nax];
	DSU() {
		for(int i=0; i<nax; ++i) {
			sz[i] = 1, par[i] = i;
		}
	}

	int find(int v) {
		return par[v] = (par[v]==v) ? v : find(par[v]);
	}
	void unite(int u, int v) {
		if(sz[u] < sz[v]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
	}
	bool same(int u, int v) {
		return find(u) == find(v);
	}
};
struct KRT {
	DSU T;
	vector<int>tree[nax * 2];
	int N;
	int r[nax];

	KRT() {
		for(int i=0; i<nax; ++i) {
			r[i] = i;
		}
	}

	void add_edge(int u, int v) {
		if(T.same(u, v)) return;
		u = T.find(u), v = T.find(v);
		tree[N].push_back(r[u]);
		tree[N].push_back(r[v]);
		T.unite(u, v);

		r[T.find(u)] = N++;
	}
	int get_rep(int v) {
		return r[T.find(v)];
	}

} krt1, krt2;
struct BIT {
	int bit[nax];

	void add(int p) {
		while(p<nax) {
			bit[p]++;
			p += p & -p;
		}
	}
	int get(int p) {
		int ret = 0;
		while(p) {
			ret += bit[p];
			p -= p & -p;
		}
		return ret;
	}
	int get(int l, int r) {
		int ret = get(r);
		if(l) ret -= get(l-1);
		return ret;
	}
};

void DFS(int v, KRT *krt, pair<int,int> *co, int N) {
	co[v].first = tt;

	tt += v < N;
	for(int u : krt->tree[v]) {
		DFS(u, krt, co, N);
	}
	co[v].second = tt-1;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

	int Q = S.size();
	int M = X.size();
	
	vector<pair<int,int>>edges;
	for(int i=0; i<M; ++i) {
		edges.emplace_back(X[i], Y[i]);
	}



	//build KRT1
	krt1.N = N;
	sort(edges.begin(), edges.end(), [&] (auto x, auto y) {
		return min(x.first, x.second) > min(y.first, y.second);
	});

	vector<int>whosL[nax];
	for(int i=0; i<Q; ++i) {
		whosL[L[i]].push_back(i);
	}

	for(int i=0; i<Q; ++i) {
		rep1[i] = S[i];
	}
	int at = 0;
	for(int i=N-1; i>=0; --i) {
		if(at < M && min(edges[at].first, edges[at].second)==i) {
			krt1.add_edge(edges[at].first, edges[at].second);
			++at;
			++i;
			continue;
		}
		for(int j : whosL[i]) {
			rep1[j] = krt1.get_rep(S[j]);
		}
	}


	//build KRT2
	krt2.N = N;
	sort(edges.begin(), edges.end(), [&] (auto x, auto y) {
		return max(x.first, x.second) < max(y.first, y.second);
	});	

	vector<int>whosR[nax];
	for(int i=0; i<Q; ++i) {
		whosR[R[i]].push_back(i);
	}

	for(int i=0; i<Q; ++i) {
		rep2[i] = E[i];
	}

	at = 0;
	for(int i=0; i<N; ++i) {
		if(at < M && max(edges[at].first, edges[at].second)==i) {
			krt2.add_edge(edges[at].first, edges[at].second);
			++at;
			--i;
			continue;
		}
		for(int j : whosR[i]) {
			rep2[j] = krt2.get_rep(E[j]);
		}

	}


	//rename nodes in KRT1
	tt = 0;
	DFS(krt1.N-1, &krt1, x_co, N);

	//rename nodes in KRT2
	tt = 0;
	DFS(krt2.N-1, &krt2, y_co, N);

	//get all points
	vector<int>x_to_y[nax];
	for(int i=0; i<N; ++i) {
		x_to_y[x_co[i].first].push_back(y_co[i].first);
	}
	vector<int>left_queries[nax], right_queries[nax];
	for(int i=0; i<Q; ++i) {
		left_queries[x_co[rep1[i]].first].push_back(i);
		right_queries[x_co[rep1[i]].second].push_back(i);
	}

	//sweep line
	BIT b;
	for(int i=0; i<N; ++i) {
		//handle left side of queries
		for(int j : left_queries[i]) {
			cnt[j] -= b.get(y_co[rep2[j]].first+1, y_co[rep2[j]].second+1);
		}

		//add points
		for(int y : x_to_y[i]) {
			b.add(y+1);
		}

		//handle right side of queries
		for(int j : right_queries[i]) {
			cnt[j] += b.get(y_co[rep2[j]].first+1, y_co[rep2[j]].second+1);
		}
	}

	//conclusion
	vector<int>ans(Q);
	for(int i=0; i<Q; ++i) {
		ans[i] = cnt[i] > 0;
	}
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51