Submission #1029751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029751		parsadox2	Werewolf (IOI18_werewolf)	C++17	34 / 100	1897 ms	38596 KiB

werewolf

#include  <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 2e5 + 10;

int n , m , q , pos[N];
vector <int> adj[N] , vec;

struct SEG{
	int mn[N << 2] , mx[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr - nl == 1)
		{
			mn[node] = mx[node] = vec[nl];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		mn[node] = min(mn[lc] , mn[rc]);
		mx[node] = max(mx[lc] , mx[rc]);
	}
	int Getmn(int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr <= l || r <= nl)
			return n;
		if(l <= nl && nr <= r)
			return mn[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		return min(Getmn(l , r , lc , nl , mid) , Getmn(l , r , rc , mid , nr));
	}
	int Getmx(int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr <= l || r <= nl)
			return 0;
		if(l <= nl && nr <= r)
			return mx[node];
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		return max(Getmx(l , r , lc , nl , mid) , Getmx(l , r , rc , mid , nr));
	}
} seg;

pair<int , int> Getst(int id , int val)
{
	pair<int , int> res;
	int low = -1 , high = id;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(seg.Getmn(mid , id + 1) >= val)
			high = mid;
		else
			low = mid;
	}
	res.first = high;
	low = id;  high = n;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(seg.Getmn(id , mid + 1) >= val)
			low = mid;
		else
			high = mid;
	}
	res.second = low;
	return res;
}

pair<int , int> Getfn(int id , int val)
{
	pair<int , int> res;
	int low = -1 , high = id;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(seg.Getmx(mid , id + 1) <= val)
			high = mid;
		else
			low = mid;
	}
	res.first = high;
	low = id;  high = n;
	while(high - low > 1)
	{
		int mid = (low + high) >> 1;
		if(seg.Getmx(id , mid + 1) <= val)
			low = mid;
		else
			high = mid;
	}
	res.second = low;
	return res;
}

vector <int> check_validity(int nn , vector <int> X , vector <int> Y , vector <int> S , vector <int> E , vector <int> L , vector <int> R )
{
	vector <int> res;
	n = nn;
	m = X.size();
	q = S.size();
	for(int i = 0 ; i < m ; i++)
	{
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}
	for(int i = 0 ; i < n ; i++)   if(adj[i].size() == 1)
	{
		vec.push_back(i);
		vec.push_back(adj[i][0]);
		break; 
	}
	while(vec.size() < n)
	{
		if(adj[vec.back()][0] == vec[vec.size() - 2])
			vec.push_back(adj[vec.back()][1]);
		else
			vec.push_back(adj[vec.back()][0]);
	}
	for(int i = 0 ; i < n ; i++)
		pos[vec[i]] = i;
	seg.Build();
	for(int i = 0 ; i < q ; i++)
	{
		pair<int ,int> a = Getst(pos[S[i]] , L[i]) , b = Getfn(pos[E[i]] , R[i]);
		bool flg = true;
		if(a.second < b.first || b.second < a.first)
			flg = false;
		res.push_back(flg);
	}
	return res;
}

Compilation message (stderr)

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:114:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |  while(vec.size() < n)
      |        ~~~~~~~~~~~^~~

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