Submission #123749

#	Time	Username	Problem	Language	Result	Execution time	Memory
123749		TuGSGeReL	Werewolf (IOI18_werewolf)	C++17	0 / 100	2120 ms	524288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
 
int cnt[200001], mntr[600001], mxtr[600001], pos[200001];
vector <int> arr, edg[200001], ans;
 
void build(int node, int l, int r)
{
	if ( l == r )
	{
		mxtr[node] = arr[l - 1];
		mntr[node] = arr[l - 1];
		return;
	}
	
	int mid = (l + r) / 2;
	
	build(node * 2, l, mid);
	build(node * 2 + 1, mid + 1, r);
	
	mxtr[node] = max(mxtr[node * 2], mxtr[node * 2 + 1]);
	mntr[node] = min(mntr[node * 2], mntr[node * 2 + 1]);
}
 
int mx(int node, int l, int r, int L, int R)
{
	if ( l > R || r < L )
		return 0;
	
	if ( l >= L && r <= R )
		return mxtr[node];
	
	int mid = (l + r) / 2;
	
	return max(mx(node * 2, l, mid, L, R), mx(node * 2 + 1, mid + 1, r, L, R));
}
 
int mn(int node, int l, int r, int L, int R)
{
	if ( l > R || r < L )
		return 1e9;
	
	if ( l >= L && r <= R )
		return mntr[node];
	
	int mid = (l + r) / 2;
	
	return min(mn(node * 2, l, mid, L, R), mn(node * 2 + 1, mid + 1, r, L, R));
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	for (int i = 0; i < X.size(); i++)
	{
		edg[X[i]].pub(Y[i]);
		edg[Y[i]].pub(X[i]);
		cnt[X[i]]++;
		cnt[Y[i]]++;
	}
	
	for (int i = 0; i < N; i++)
	{
		if ( cnt[i] == 1 )
		{
			queue<pii> q;
			q.push(mp(i, -1));
			
			while (!q.empty())
			{
				int u = q.front().ff;
				int par = q.front().ss;
				q.pop();
				arr.pub(u);
				pos[u] = arr.size();
				
				for (auto v : edg[u])
					if ( v != par )
						q.push(mp(v, u));
			}
			
			break;
		}
	}
	
	build(1, 1, N);
	
	for (int i = 0; i < S.size(); i++)
	{
		if ( pos[S[i]] < pos[E[i]] )
		{
			int l = pos[S[i]], r = pos[E[i]], Ls = -1, Le = -1;
			
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				
				if ( mn(1, 1, N, pos[S[i]], mid) >= L[i] )
					l = mid;
				
				else
					r = mid;
			}
			
			if ( mn(1, 1, N, pos[S[i]], r) >= L[i] )
				Ls = r;
			
			else if ( mn(1, 1, N, pos[S[i]], l) >= L[i] )
				Ls = l;
				
			l = pos[S[i]], r = pos[E[i]];
			
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				
				if ( mx(1, 1, N, mid, pos[E[i]]) <= R[i] )
					r = mid;
				
				else
					l = mid;
			}
			
			if ( mx(1, 1, N, l, pos[E[i]]) <= R[i] )
				Le = l;
			
			else if ( mx(1, 1, N, r, pos[E[i]]) <= R[i] )
				Le = r;
			
			cout << Ls << " " << Le << "\n";
			
			if ( Ls >= Le && Ls != -1 && Le != -1 )
				ans.pub(1);
			
			else
				ans.pub(0);
		} else {
			int l = pos[E[i]], r = pos[S[i]], Ls = -1, Le = -1;
			
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				
				if ( mn(1, 1, N, mid, pos[S[i]]) >= L[i] )
					r = mid;
				
				else
					l = mid;
			}
			
			if ( mn(1, 1, N, pos[S[i]], l) >= L[i] )
				Ls = l;
			
			else if ( mn(1, 1, N, pos[S[i]], r) >= L[i] )
				Ls = r;
				
			l = pos[S[i]], r = pos[E[i]];
			
			while (l + 1 < r)
			{
				int mid = (l + r) / 2;
				
				if ( mx(1, 1, N, pos[E[i]], mid) <= R[i] )
					l = mid;
				
				else
					r = mid;
			}
			
			if ( mx(1, 1, N, pos[E[i]], r) <= R[i] )
				Le = r;
			
			else if ( mx(1, 1, N, pos[E[i]], l) <= R[i] )
				Le = l;
			
			if ( Ls <= Le && Ls != -1 && Le != -1 )
				ans.pub(1);
			
			else
				ans.pub(0);
		}
	}
	
	return ans;
}

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:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++)
                  ~~^~~~~~~~~~
werewolf.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++)
                  ~~^~~~~~~~~~

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