Submission #139944

#	Time	Username	Problem	Language	Result	Execution time	Memory
139944		vince	Werewolf (IOI18_werewolf)	C++14	34 / 100	1206 ms	71268 KiB

werewolf

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>

using namespace std;

#define long long long
#define fi first
#define se second
typedef pair<int,int> ii;


int n, m, q;
int L[200003], R[200003], S[200003], E[200003];
bool visited[200003][2];
vector<int> vec[200003];

void dfs(int u, int x, int l, int r)
{
	// printf("%d %d %d %d\n", u, x, l, r);
	visited[u][x] = 1;
	if(x == 0 && !visited[u][1] && l <= u && u <= r)
		dfs(u,1, l, r);
	
	for(int v : vec[u])
	{
		if(x == 0 && v >= l && !visited[v][0])
			dfs(v,0, l, r);
		if(x == 1 && v <= r && !visited[v][1])
			dfs(v,1, l, r);
	} 
}

vector<int> solve_small()
{
	vector<int> ans;
  	for(int i = 0; i < q; i++)
  	{
  		for(int j = 0; j < n; j++)
  			visited[j][0] = visited[j][1] = 0;

  		dfs(S[i], 0, L[i], R[i]);
  		ans.push_back(visited[E[i]][1]);
  	}
  	return ans;
}

int A[200003];
int id[200003];
int sz = 0;
int Tx[200003][20], Tn[200003][20];
int lg[200003];
void create_line(int u)
{
	visited[u][0] = 1;
	A[sz] = u;
	id[u] = sz++;

	for(int v : vec[u])
		if(!visited[v][0])
			create_line(v);
}

void build()
{
	for(int i = 1; i <= 200000; i++)
		lg[i] = log2(i);
	for(int i = 0; i < 20; i++)
		for(int j = 0; j+(1<<i)-1 < n; j++)
			Tn[j][i] = (i == 0)? A[j] : min(Tn[j][i-1], Tn[j+(1<<(i-1))][i-1]);

	for(int i = 0; i < 20; i++)
		for(int j = 0; j+(1<<i)-1 < n; j++)
			Tx[j][i] = (i == 0)? A[j] : max(Tx[j][i-1], Tx[j+(1<<(i-1))][i-1]);
}

int MAX(int kir, int kan)
{
	int len = kan-kir+1;
	int x = lg[len];
	return max(Tx[kir][x], Tx[kan-(1<<x)+1][x]);
}

int MIN(int kir, int kan)
{
	int len = kan-kir+1;
	int x = lg[len];
	return min(Tn[kir][x], Tn[kan-(1<<x)+1][x]);
}

vector<int> solve_line()
{
	vector<int> ans;
	for(int i = 0; i < n; i++)
	{
		if(vec[i].size() == 1)
		{
			create_line(i);
			break;
		}
	}

	build();
	// for(int i = 0; i < n; i++) printf("%d ", A[i]); printf("\n");
	// for(int i = 0; i < n; i++) printf("%d ", id[i]); printf("\n");

	for(int i = 0; i < q; i++)
	{
		int x = id[S[i]], y = id[E[i]];
		// printf("%d %d\n", x, y);

		int kir1 = 0, kan1 = x;
		while(kir1 < kan1)
		{
			int mid = (kir1+kan1)/2;
			if(MIN(mid, x) >= L[i]) kan1 = mid;
			else kir1 = mid+1;
		}

		int kir2 = x, kan2 = n-1;
		while(kir2 < kan2)
		{
			int mid = (1+kir2+kan2)/2;
			if(MIN(x, mid) >= L[i]) kir2 = mid;
			else kan2 = mid-1;
		}

		int kir3 = 0, kan3 = y;
		while(kir3 < kan3)
		{
			int mid = (kir3+kan3)/2;
			if(MAX(mid, y) <= R[i]) kan3 = mid;
			else kir3 = mid+1;
		}

		int kir4 = y, kan4 = n-1;
		while(kir4 < kan4)
		{
			int mid = (1+kir4+kan4)/2;
			if(MAX(y, mid) <= R[i]) kir4 = mid;
			else kan4 = mid-1;
		}
		if(kir4 < kir1 || kir2 < kir3) ans.push_back(0);
		else ans.push_back(1);
	}
	return ans;
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> _S, vector<int> _E,
                                vector<int> _L, vector<int> _R) 
{
  	n = N;
  	m = X.size();
  	q = _S.size();
  	for(int i = 0; i < m; i++)
  	{
  		vec[X[i]].push_back(Y[i]);
  		vec[Y[i]].push_back(X[i]);
  	}
  	for(int i = 0; i < q; i++)
  		S[i] = _S[i], L[i] = _L[i], R[i] = _R[i], E[i] = _E[i];
  	
	if(n <= 3000 && m <= 6000 && q <= 3000 && 0) return solve_small();
	else return solve_line();
}

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