Submission #333603

#	Time	Username	Problem	Language	Result	Execution time	Memory
333603		nicholask	Werewolf (IOI18_werewolf)	C++14	15 / 100	4058 ms	23788 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
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 m=x.size(),q=s.size();
	vector <int> g[n];
	for (int i=0; i<m; i++){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	vector <int> res;
	for (int i=0; i<q; i++){
		bool visited[n];
		for (int j=0; j<n; j++) visited[j]=0;
		queue <int> q;
		if (s[i]>=l[i]){
			q.push(s[i]);
			visited[s[i]]=1;
		}
		while (!q.empty()){
			int t=q.front();
			q.pop();
			for (auto&j:g[t]){
				if (j>=l[i]&&!visited[j]){
					q.push(j);
					visited[j]=1;
				}
			}
		}
		bool visited1[n];
		for (int j=0; j<n; j++) visited1[j]=0;
		if (e[i]<=r[i]){
			q.push(e[i]);
			visited1[e[i]]=1;
		}
		while (!q.empty()){
			int t=q.front();
			q.pop();
			for (auto&j:g[t]){
				if (j<=r[i]&&!visited1[j]){
					q.push(j);
					visited1[j]=1;
				}
			}
		}
		bool can=0;
		for (int j=0; j<n; j++){
			if (visited[j]&&visited1[j]){
				can=1;
				break;
			}
		}
		res.push_back(can);
	}
	return res;
}

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