Submission #706983

#	Time	Username	Problem	Language	Result	Execution time	Memory
706983		Abrar_Al_Samit	Werewolf (IOI18_werewolf)	C++17	34 / 100	901 ms	76500 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;

const int nax = 2e5 + 10;
vector<int>a[nax], b[nax];
bool vis[nax];

vector<int>stk;
void dfs(int v) {
	vis[v] = 1;
	stk.push_back(v);
	for(int u : a[v]) if(!vis[u]) {
		dfs(u);
	}
}
vector<int>ord;

template<const int type> struct SparseTable {
	int sp[nax][18];
	int N;

	int F(int a, int b) {
		if(type==1) return max(a, b);
		else return min(a, b);
	}
	void build(vector<int>init) {
		N = init.size();
		for(int i=0; i<N; ++i) {
			sp[i][0] = init[i];
		}
		for(int j=1; j<18; ++j) {
			for(int i=0; i+(1<<(j-1))-1<N; ++i) {
				sp[i][j] = F(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
			}
		}
	}
	pair<int,int>get(int pos, int lim) {
		int l = pos, r = pos;
		for(int j=17; j>=0; --j) {
			int new_pos = l - (1<<j);
			if(new_pos<0) continue;

			if(sp[new_pos][j]<lim && type==2) continue;
			if(sp[new_pos][j]>lim && type==1) continue;
			l = new_pos;
		}
		for(int j=17; j>=0; --j) {
			int new_pos = r + (1<<j);
			if(new_pos>=N) continue;

			if(sp[r][j]<lim && type==2) continue;
			if(sp[r][j]>lim && type==1) continue;

			// if(type==1) {
			// 	cerr<<r<<' '<<new_pos<<'\n';
			// }

			r = new_pos;
		}
		if(sp[l][0]<lim && type==2) ++l;
		else if(sp[l][0]>lim && type==1) ++l;

		if(sp[r][0]<lim && type==2) --r;
		else if(sp[r][0]>lim && type==1) --r;

		return make_pair(l, r);
	}
};
SparseTable<1>big;
SparseTable<2>small;
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<int>ans(q);


	for(int i=0; i<m; ++i) {
		a[X[i]].push_back(Y[i]);
		a[Y[i]].push_back(X[i]);
	}

	memset(vis, 0, sizeof vis);
	for(int i=0; i<N; ++i) if(a[i].size()==1) {
		dfs(i);
		ord = stk;
		break;
	}

	//for(int x : ord) cerr<<x<<' '; cerr<<'\n';


	vector<int>invord(N);
	for(int i=0; i<N; ++i) {
		invord[ord[i]] = i;
	}

	big.build(ord), small.build(ord);

	for(int i=0; i<q; ++i) {
		auto [l1, r1] = small.get(invord[S[i]], L[i]);
		auto [l2, r2] = big.get(invord[E[i]], R[i]);

		//cerr<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<'\n';

		if(l1>=l2 && l1<=r2) ans[i] = 1;
		else if(l2>=l1 && l2<=r1) ans[i] = 1;
	}
	return ans;
}

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