제출 #831409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831409		caganyanmaz	늑대인간 (IOI18_werewolf)	C++17	0 / 100	252 ms	524288 KiB

werewolf

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

//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 2e5;
constexpr static int MXST = MXN<<1;
constexpr static int INF = 1e6;
using namespace std;

struct SegTree
{
	int def;
	function<int(int, int)> merge;
	int n;
	int v[MXN];
	void build(int n, int* a, function<int(int, int)> merge, int def)
	{
		this->n = n;
		this->merge = merge;
		this->def = def;
		for (int i = n; i < 2*n; i++) v[i] = a[i-n];
		for (int i = n-1; i > 0; i--) v[i] = merge(v[i<<1], v[(i<<1)|1]);
	}
	int get(int l, int r)
	{
		int res = def;
		for (l+=n,r+=n;r>l;r>>=1,l>>=1)
		{
			if (l&1) res = merge(res, v[l++]);
			if (r&1) res = merge(res, v[--r]);
		}
		return res;
	}

};


int v[MXN];
int p[MXN];
vector<int> g[MXN];

void find_p(int node, int pr, int current)
{
	p[node] = current;
	for (int c : g[node])
		if (c != pr)
			find_p(c, node, current+1);
}

SegTree mnst, mxst;

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++)
	{
		g[x[i]].pb(y[i]);
		g[y[i]].pb(x[i]);
	}
	for (int i = 0; i < n; i++)
	{
		if (g[i].size() == 1)
		{
			find_p(i, -1, 0);
			break;
		}
	}
	for (int i = 0; i < n; i++)
	{
		v[p[i]] = i;
	}
	auto mnop = [] (int a, int b) -> int { return min(a, b); };
	auto mxop = [] (int a, int b) -> int { return max(a, b); };
	mnst.build(n, v, mnop, INF);
	mxst.build(n, v, mxop, -1);
	vector<int> res;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] < L[i] || e[i] > R[i])
		{
			res.pb(0);
			continue;
		}
		if (p[e[i]] > p[s[i]])
		{
			int l = -1, r = n+1;
			while (r - l > 1)
			{
				int m = l+r>>1;
				if (mnst.get(p[s[i]], m) < L[i])
					r = m;
				else
					l = m;
			}
			debug(mnst.get(1, 2));
			debug(0, l, r);
			int ll = l;
			l = -1, r = n+1;
			while (r - l > 1)
			{
				int m = l+r>>1;
				if (mxst.get(m, p[e[i]]) > R[i])
					l = m;
				else
					r = m;
			}
			debug(1, l, r);
			debug(s[i], e[i], ll, r);
			res.pb(ll > r ? 1 : 0);
		}
		else
		{
			int l = -1, r = n+1;
			while (r - l > 1)
			{
				int m = l+r>>1;
				if (mxst.get(p[e[i]], m) > R[i])
					r = m;
				else
					l = m;
			}
			debug(2, l, r);
			debug(p[e[i]], l, mxst.get(p[e[i]], l));
			int ll = l;
			l = -1, r = n+1;
			while (r - l > 1)
			{
				int m = l+r>>1;
				if (mnst.get(m, p[s[i]]) < L[i])
					l = m;
				else
					r = m;
			}
			debug(3, l, r);
			debug(s[i], e[i], ll, r);
			res.pb(ll > r ? 1 : 0);
		}
	}
	return res;

}

컴파일 시 표준 에러 (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:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < x.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
werewolf.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int m = l+r>>1;
      |             ~^~
werewolf.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int m = l+r>>1;
      |             ~^~
werewolf.cpp:121:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |     int m = l+r>>1;
      |             ~^~
werewolf.cpp:133:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |     int m = l+r>>1;
      |             ~^~

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