Submission #132028

#	Time	Username	Problem	Language	Result	Execution time	Memory
132028		dvdg6566	Werewolf (IOI18_werewolf)	C++14	15 / 100	355 ms	28152 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi>vpi;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define MAXN 3010

vi V[MAXN];
int N,M,Q,a,b;
bool A[MAXN][2];
int W[MAXN];
int vis[MAXN];

void dfs(int x, int l){
	// cout<<"DFS "<<x<<' '<<l<<'\n';
	A[x][0]=1;
	for (auto v:V[x])if (vis[v] == 0 && v >= l){
		vis[v]=1;
		dfs(v,l);
	}
}

void dfs2(int x, int r){
	A[x][1]=1;
	for (auto v:V[x])if (vis[v] == 0 && v <= r){
		vis[v]=1;
		dfs2(v,r);
	}
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	Q = SZ(S);M=SZ(X);
	for (int i=0;i<M;++i){
		a=X[i];b=Y[i];
		V[a].pb(b);
		V[b].pb(a);
	}
	vi out(Q,0);
	for (int i=0;i<Q;++i){
		memset(vis,0,sizeof(vis));
		memset(A,0,sizeof(A));
		dfs(S[i],L[i]);
		memset(vis,0,sizeof(vis));
		dfs2(E[i],R[i]);

		// for (int i=0;i<N;++i)cout<<A[i][0]<<' ';cout<<'\n';
		// for (int i=0;i<N;++i)cout<<A[i][1]<<' ';cout<<'\n';
		// cout<<'\n';

		for (int x=0;x<N;++x)if (A[x][0] && A[x][1])out[i]=1;
	}
  	return out;
}

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