Submission #1043009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043009		XJP12	Werewolf (IOI18_werewolf)	C++14	15 / 100	4082 ms	39296 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi ;
vvi g;
bitset<200005> vis;
bitset<200005> vis1;
bool ban=false;
void dfs2(int u, int l){
	if(u>l) return;
	vis1[u]=true;
	if(vis[u]==true && vis1[u]==true){
		ban=true;
	}
	for(auto v: g[u]){
		if(!vis1[v]){
			dfs2(v,l);
		}
	}
}
void dfs1(int u, int l){
	if(u<l) return;
	vis[u]=true;
	for(auto v: g[u]){
		if(!vis[v]){
			dfs1(v,l);
		}
	}
}
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++){
		vis.reset();
		vis1.reset();
		ban=false;
		dfs1(s[i], l[i]);
		dfs2(e[i], r[i]);
		if(ban){
			ans[i]=1;
		}
	}
	return ans;

}

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