oj.uz

답안 #831416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831416 2023-08-20T08:43:46 Z caganyanmaz 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1106 ms 524288 KB 
#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 = 3e5;
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[MXST];
	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;
		l = max(l, 0);
		r = min(r, n);
		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;
			}
			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;
			}
			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;
			}
			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;
			}
			res.pb(ll > r ? 1 : 0);
		}
	}
	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:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  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:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int m = l+r>>1;
      |             ~^~
werewolf.cpp:117:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |     int m = l+r>>1;
      |             ~^~
werewolf.cpp:127:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int m = l+r>>1;
      |             ~^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 248 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 248 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 544 ms 34036 KB Output is correct
2 Correct 1092 ms 42488 KB Output is correct
3 Correct 1106 ms 42484 KB Output is correct
4 Correct 1008 ms 42532 KB Output is correct
5 Correct 965 ms 42504 KB Output is correct
6 Correct 735 ms 42440 KB Output is correct
7 Correct 892 ms 42452 KB Output is correct
8 Correct 1096 ms 42492 KB Output is correct
9 Correct 583 ms 42456 KB Output is correct
10 Correct 686 ms 42532 KB Output is correct
11 Correct 688 ms 42552 KB Output is correct
12 Correct 470 ms 42572 KB Output is correct
13 Correct 1041 ms 42652 KB Output is correct
14 Correct 1027 ms 42528 KB Output is correct
15 Correct 1025 ms 42496 KB Output is correct
16 Correct 1033 ms 42460 KB Output is correct
17 Correct 914 ms 42504 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 248 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -