Submission #1042976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042976		XJP12	Werewolf (IOI18_werewolf)	C++14	7 / 100	4067 ms	22704 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi ;
vvi g;
bitset<200005> vis;
bool ban=false;
bool hw=false;
void dfs(int u, int l, int r, int j, int fin){
	vis[u]=true;
	if(u==j && u<=r){
		ban=true;
	}
	if(u==fin && ban==true){
		hw=true;
	}
	for(auto v: g[u]){
		if(u==j && u>r) break;
		if(!vis[v]){
			if(!ban){
				if(v>=l) dfs(v,l,r,j, fin);
			}else{
				if(v<=r) dfs(v,l,r,j, fin);
			}
		}
	}
	if(u==j){
		ban=false;
	}
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){
	int m = (int)x.size();
	int q = (int)e.size();
	vi ans(q,0);
	g.resize(n, vi());
	for(int i=0; i<m; i++){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	for(int i=0; i<q; i++){
		for(int j=0; j<n; j++){
		    ban=false;
			hw=false;
			vis.reset();
			dfs(s[i], l[i], r[i], j, e[i]);
			if(vis[e[i]]==true && hw==true){
				ans[i]=1;
			}
		}
	}
	return ans;

}

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