oj.uz

답안 #138226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138226 2019-07-29T15:44:03 Z Lawliet 늑대인간 (IOI18_werewolf) C++14
0 / 100
 1519 ms 55460 KB 
#include <bits/stdc++.h>

#define LOG 20
#define MAX 200010
#define INF 1000000000

using namespace std;

int N, M, Q;

int v[MAX];
int ind[MAX];
int mn[MAX][LOG];
int mx[MAX][LOG];

vector<int> ans;

vector<int> grafo[MAX];

void preProcess()
{
	for(int g = 0 ; g < N ; g++)
		mn[g][0] = mx[g][0] = v[g];

	for(int k = 1 ; k < LOG ; k++)
	{
		for(int g = 0 ; g < N ; g++)
		{
			int jump = g + (1 << k) - 1;

			if(jump >= N) continue;//VER ISSO

			mn[g][k] = min(mn[g][k - 1] , mn[jump][k - 1]);
			mx[g][k] = max(mx[g][k - 1] , mx[jump][k - 1]);
		}
	}
}

int getMin(int L, int R)
{
	if(L > R) swap(L , R);

	int sz = R - L + 1;

	float aux = log2( sz );//ver caso = 0 ou = 1
	int logarithm = (int) aux;

	int pot = (1 << logarithm);

	int i = R + 1 - pot;

	return min(mn[L][logarithm] , mn[i][logarithm]);
}

int getMax(int L, int R)
{
	if(L > R) swap(L , R);

	int sz = R - L + 1;

	float aux = log2( sz );//ver caso = 0 ou = 1
	int logarithm = (int) aux;

	int pot = (1 << logarithm);

	int i = R + 1 - pot;

	return max(mx[L][logarithm] , mx[i][logarithm]);
}

bool test(int i, int j, int k, bool isMax)
{
	if(isMax)
	{
		int aux = getMax(i , j);
		return k >= aux;
	}
	else
	{
		int aux = getMin(i , j);
		return k <= aux;
	}
}

int bs(int i, int k, bool t, bool isMax)//t TRUE É ESQUERDA//ISMAX MAIOR QUE K
{
	int l, r;

	if(!t)
	{
		l = i;
		r = N - 1;

		//if(!test(l , l , k , isMax)) return -INF;
	}
	else
	{
		l = 0;
		r = i;

		//if(!test(r , r , k , isMax)) return INF;
	}

	//FAZER TESTE INICIO

	while(l < r)
	{
		int m = (l + r)/2;
		if(!t && l == r - 1) m = r;

		bool aux = test(i , m , k , isMax);

		//printf("(%d,%d)  %d     %d               %d %d %d %d\n",l,r,m,aux,i,k,t,isMax);

		if(aux)
		{
			if(!t) l = m;
			else r = m;
		}
		else
		{
			if(!t) r = m - 1;
			else l = m + 1;
		}
	}

	return l;
}

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 = L.size();

	for(int g = 0 ; g < M ; g++)
	{
		int i = X[g];
		int j = Y[g];

		grafo[ i ].push_back( j );
		grafo[ j ].push_back( i );

		//printf("ooooooooooooooooooooooooooooo %d %d\n",i,j);
	}

	int cur, pai = -1;

	for(int g = 0 ; g < N ; g++)
		if(grafo[g].size() == 1) cur = g;

	for(int g = 0 ; g < N ; g++)
	{
		v[ g ] = cur;
		ind[ cur ] = g;

		//printf("== %d\n",cur);

		for(int h = 0 ; h < grafo[cur].size() ; h++)
		{
			//printf("-> %d\n",h);
			int prox = grafo[cur][h];

			//printf("prox = %d\n",prox);

			if(prox == pai) continue;

			pai = cur;
			cur = prox;
			break;
		}
	}

	//printf("\noi\n");

	preProcess();

	//printf("passei\n");

	for(int curQuery = 0 ; curQuery < Q ; curQuery++)
	{
		bool canTransform = false;

		int start = ind[ S[ curQuery ] ];
		int end = ind[ E[ curQuery ] ];

		if(start < end)
		{
			int maxHuman = bs(start , L[ curQuery ] , false , false);//TRUE É PARA A ESQUERDA
			int minWerewolf = bs(end , R[ curQuery ] , true , true);

			//printf("P %d %d\n",maxHuman,minWerewolf);

			if(minWerewolf <= maxHuman) canTransform = true;
		}
		else
		{
			int minHuman = bs(start , L[ curQuery ] , true , false); //printf("\n\n");
			int maxWerewolf = bs(end , R[ curQuery ] , false , true);

			//printf("S %d %d\n",minHuman,maxWerewolf);

			if(minHuman <= maxWerewolf) canTransform = true;
		}

		if(canTransform) ans.push_back( 1 );
		else ans.push_back( 0 );

		//printf("\n\n");
	}

	return ans;
}

/*int main()
{
	int nn, qq, mm;
	scanf("%d %d %d",&nn,&mm,&qq);

	vector<int> xx(mm), yy(mm);
	vector<int> ss(qq), ee(qq), ll(qq), rr(qq);

	for(int g = 0 ; g < mm ; g++)
		scanf("%d %d",&xx[g],&yy[g]);

	for(int g = 0 ; g < qq ; g++)
		scanf("%d %d %d %d",&ss[g],&ee[g],&ll[g],&rr[g]);

	vector<int> final = check_validity(nn , xx , yy , ss , ee , ll , rr);

	for(int g = 0 ; g < qq ; g++)
		printf("%d ",final[g]);
}*/

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:157:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < grafo[cur].size() ; h++)
                   ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:145:6: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int cur, pai = -1;
      ^~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1519 ms 55460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -