oj.uz

Submission #138224

# Submission time Handle Problem Language Result Execution time Memory
138224 2019-07-29T15:42:33 Z Lawliet Werewolf (IOI18_werewolf) C++14
0 / 100
 1114 ms 61036 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 );
	}
 
	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 ",cur);
 
		for(int h = 0 ; h < grafo[cur].size() ; h++)
		{
			int prox = grafo[cur][h];
 
			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:155:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0 ; h < grafo[cur].size() ; h++)
                   ~~^~~~~~~~~~~~~~~~~~~
werewolf.cpp:143:6: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int cur, pai = -1;
      ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1114 ms 61036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -