Submission #706219

#	Time	Username	Problem	Language	Result	Execution time	Memory
706219		Abrar_Al_Samit	Werewolf (IOI18_werewolf)	C++17	0 / 100	4021 ms	50756 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>stk1, stk2;

// void dfs1(int v) {
// 	vis[v] = 1;
// 	stk1.push_back(v);
// 	for(int u : a[v]) if(!vis[u]) {
// 		dfs1(u);
// 	}
// }
// void dfs2(int v) {
// 	vis[v] = 1;
// 	stk2.push_back(v);
// 	for(int u : b[v]) if(!vis[u]) {
// 		dfs2(u);
// 	}
// }

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;

struct node {
	int mn, mx;
	node() {}
	node(int i) {
		mn = mx = ord[i];
	}
	node(int x, int y) {
		mn = x, mx = y;
	}
} tree[nax * 4];

node merge(node x, node y) {
	node ret;
	ret.mn = min(x.mn, y.mn);
	ret.mx = max(x.mx, y.mx);
	return ret;
}
void build(int l, int r, int v) {
	if(l==r) {
		tree[v] = node(l-1);
		return;
	}
	int mid = (l+r)/2;
	build(l, mid, v*2), build(mid+1, r, v*2+1);
	tree[v] = merge(tree[v*2], tree[v*2+1]);
}
node query(int l, int r, int L, int R, int v) {
	if(l>=L && r<=R) return tree[v];
	if(l>R || r<L) return node(1e9, -1e9);

	int mid = (l+r)/2;
	return merge(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+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<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;
	}


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


	for(int i=0; i<q; ++i) {
		vector<pair<int,int>>bag;

		bool f = true;
		for(int x : {S[i], E[i]}) {
			int l = 0, r = N - invord[x] - 1;
			while(l<r) {
				int mid = (l+r+1)/2;
				node cr = query(1, N, invord[x]+1, invord[x]+mid+1, 1);
				if(f) {
					if(cr.mn>=L[i]) {
						l = mid;
					} else {
						r = mid-1;
					}
				} else {
					if(cr.mx<=R[i]) {
						l = mid;
					} else {
						r = mid-1;
					}
				}
			}
			int rit = invord[x] + l;

			l = 0, r = invord[x];
			while(l<r) {
				int mid = (l+r+1)/2;
				node cr = query(1, N, invord[x]-mid+1, invord[x]+1, 1);
				if(f) {
					if(cr.mn>=L[i]) {
						l = mid;
					} else {
						r = mid-1;
					}
				} else {
					if(cr.mx<=R[i]) {
						l = mid;
					} else {
						r = mid-1;
					}
				}
			}
			int lef = invord[x] - l;
			bag.emplace_back(lef, rit);
			f = false;

		}
		if(bag[0].first>=bag[1].first && bag[0].first<=bag[1].second) {
			ans[i] = 1;
		} else if(bag[1].first>=bag[0].first && bag[1].first<=bag[0].second) {
			ans[i] = 1;
		}
	}
	return ans;

	// for(int i=0; i<q; ++i) {
	// 	for(int j=0; j<N; ++j) {
	// 		a[j].clear(), b[j].clear();
	// 	}
	// 	for(int j=0; j<m; ++j) {
	// 		int u = X[j], v = Y[j];
	// 		if(min(u, v) >= L[i]) {
	// 			a[u].push_back(v);
	// 			a[v].push_back(u);
	// 		} 
	// 		if(max(u, v) <= R[i]) {
	// 			b[u].push_back(v);
	// 			b[v].push_back(u);
	// 		}
	// 	}

	// 	stk1.clear(), stk2.clear();

	// 	memset(vis, 0, sizeof vis);		
	// 	dfs1(S[i]);
	// 	memset(vis, 0, sizeof vis);
	// 	dfs2(E[i]);

	// 	int cnt[N] = {0};
	// 	for(int x : stk1) {

	// 		if(x>=L[i] && x<=R[i]) {
	// 			cnt[x]++;
	// 		}
	// 	}
	// 	for(int x : stk2) {
	// 		if(x>=L[i] && x<=R[i]) {
	// 			cnt[x]++;
	// 			if(cnt[x]>1) {
	// 				ans[i] = 1;
	// 			}
	// 		}
	// 	}
	// }
	// return ans;
}

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