제출 #212634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212634		MarcoMeijer	Werewolf (IOI18_werewolf)	C++14	49 / 100	1370 ms	55176 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX=5e5;
int M, Q, N;
vi adj[MX];
vi A, B, SEGMIN, SEGMAX, POSB;

void dfs(int u, int p=-1) {
	B[N++] = u;
	for(int v:adj[u]) if(v != p) dfs(v, u);
}
void buildSeg(int p=0, int l=0, int r=N-1) {
	if(l == r) {
		SEGMIN[p] = B[l];
		SEGMAX[p] = B[l];
		return;
	}
	int m=(l+r)/2;
	buildSeg(p*2+1,l,m);
	buildSeg(p*2+2,m+1,r);
	SEGMIN[p] = min(SEGMIN[p*2+1], SEGMIN[p*2+2]);
	SEGMAX[p] = max(SEGMAX[p*2+1], SEGMAX[p*2+2]);
}
int getMin(int i, int j, int p=0, int l=0, int r=N-1) {
	if(j < l || i > r) return INF;
	if(i <= l && j >= r) return SEGMIN[p];
	int m=(l+r)/2;
	int a=getMin(i,j,p*2+1,l,m);
	int b=getMin(i,j,p*2+2,m+1,r);
	return min(a,b);
}
int getMax(int i, int j, int p=0, int l=0, int r=N-1) {
	if(j < l || i > r) return -INF;
	if(i <= l && j >= r) return SEGMAX[p];
	int m=(l+r)/2;
	int a=getMax(i,j,p*2+1,l,m);
	int b=getMax(i,j,p*2+2,m+1,r);
	return max(a,b);
}
vi check_validity2(vi& X, vi& Y, vi& S, vi& E, vi& L, vi& R) {
	int start = 0;
	RE(i,N) if(adj[i].size() == 1) start = i;
	B.resize(N); N=0;
	dfs(start);
	POSB.resize(N);
	RE(i,N) POSB[B[i]] = i;

	SEGMIN.resize(N*4);
	SEGMAX.resize(N*4);
	buildSeg();

	RE(i,Q) {
		int s=POSB[S[i]], e=POSB[E[i]];
		if(s < e) {
			if(getMin(s,e) >= L[i]) {
				if(B[e] <= R[i]) A[i] = 1;
				else			 A[i] = 0;
			} else {
				int lb=s, ub=e;
				while(lb != ub) {
					int mid=(lb+ub)/2;
					if(getMin(s, mid) < L[i]) 	ub=mid;
					else 						lb=mid+1;
				}
					 if(lb == s) 				A[i] = 0;
				else if(B[lb-1] > R[i]) 		A[i] = 0;
				else if(getMax(lb, e) > R[i]) 	A[i] = 0;
				else 							A[i] = 1;
			}
		} else {
			if(getMin(e,s) >= L[i]) {
				if(B[e] <= R[i]) A[i] = 1;
				else			 A[i] = 0;
			} else {
				int lb=e, ub=s;
				while(lb != ub) {
					int mid=(lb+ub+1)/2;
					if(getMin(mid, s) < L[i]) 	lb=mid;
					else 						ub=mid-1;
				}
					 if(ub == s) 				A[i] = 0;
				else if(B[lb+1] > R[i]) 		A[i] = 0;
				else if(getMax(e, lb) > R[i]) 	A[i] = 0;
				else 							A[i] = 1;
			}
		}
	}

	return A;
}
vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
	N = n;
	M = X.size();
	Q = S.size();
	A.resize(Q);
	RE(i,M) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}

	if(N > 3000) return check_validity2(X, Y, S, E, L, R);
	bitset<6000> visited[2];

	RE(i,Q) {
		RE(j,2) visited[j].reset();
		queue<ii> q; q.push({S[i],0}); visited[0][S[i]]=1;
		while(!q.empty()) {
			ii p = q.front(); q.pop();
			int u = p.fi;
			int w = p.se;
			for(int v : adj[u]) {
				if(visited[w][v] ) continue;
				if(!w && v < L[i]) continue;
				if( w && v > R[i]) continue;
				visited[w][v] = 1;
				q.push({v,w});
			}
			if(!visited[1][u] && L[i] <= u && u <= R[i]) {
				visited[1][u] = 1;
				q.push({u,1});
			}
		}
		A[i] = visited[1][E[i]];
	}

	return A;
}

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