oj.uz

Submission #1029751

# Submission time Handle Problem Language Result Execution time Memory
1029751 2024-07-21T09:15:12 Z parsadox2 Werewolf (IOI18_werewolf) C++17
34 / 100
 1897 ms 38596 KB 
#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

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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 38340 KB Output is correct
2 Correct 1832 ms 38200 KB Output is correct
3 Correct 1744 ms 38172 KB Output is correct
4 Correct 1825 ms 38376 KB Output is correct
5 Correct 1897 ms 38336 KB Output is correct
6 Correct 1780 ms 38316 KB Output is correct
7 Correct 1789 ms 38216 KB Output is correct
8 Correct 1756 ms 38236 KB Output is correct
9 Correct 836 ms 38340 KB Output is correct
10 Correct 1276 ms 38252 KB Output is correct
11 Correct 1419 ms 38324 KB Output is correct
12 Correct 1044 ms 38344 KB Output is correct
13 Correct 1776 ms 38344 KB Output is correct
14 Correct 1738 ms 38340 KB Output is correct
15 Correct 1744 ms 38392 KB Output is correct
16 Correct 1818 ms 38596 KB Output is correct
17 Correct 1811 ms 38324 KB Output is correct

Subtask #4
0 / 51.0

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