제출 #295862

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

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5;
vector<int>vec,g[MAXN];
int pos[MAXN];
int mn[MAXN << 2], mx[MAXN << 2];
void dfs (int v, int p = -1) {
	vec.push_back (v);
	for (int to : g[v]) if (to != p) dfs (to, v);
}
void build (int l = 0, int r = vec.size(), int v = 0) {
	if (r - l == 1) { mn[v] = mx[v] = vec[l]; return; }
	int m = (l + r) >> 1;
	build (l, m, v + v + 1), build (m, r, v + v + 2);
	mn[v] = min (mn[v + v + 1], mn[v + v + 2]);
	mx[v] = max (mx[v + v + 1], mx[v + v + 2]);
}
int getmn (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
	if (L <= l && r <= R) return mn[v];
	if (L >= r || l >= R) return MAXN;
	int m = (l + r) >> 1;
	return min (getmn (L, R, l, m, v + v + 1), getmn (L, R, m, r, v + v + 2));
}
int getmx (int L, int R, int l = 0, int r = vec.size(), int v = 0) {
	if (L <= l && r <= R) return mx[v];
	if (L >= r || l >= R) return -MAXN;
	int m = (l + r) >> 1;
	return max (getmx (L, R, l, m, v + v + 1), getmx (L, R, m, r, v + v + 2));
}
vector<int> check_validity
(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int M = X.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[X[i]].push_back (Y[i]);
		g[Y[i]].push_back (X[i]);
	}
	int root;
	for (int i = 0 ; i < N ; ++ i) {
		if (g[i].size() == 1) root = i;
	}
	dfs(root);
	build();
	for (int i = 0 ; i < N ; ++ i) {
		pos[vec[i]] = i;
	}
	int Q = S.size();
	vector<int>ans(Q);
	for (int i = 0 ; i < Q ; ++ i) {
		int s = S[i], e = E[i];
		int l = pos[s], r = pos[e], res = 0;
		for (int m = l ; m <= r ; ++ m) {
			if (getmn (l, m + 1) >= L[i] && getmx (m, r + 1) <= R[i]) { res = 1; break; }
		}
		// while (l <= r) {
			// int m = (l + r) >> 1;
			// bool lf = (getmn (pos[s], m + 1) >= L[i]);
			// bool rg = (getmx (m, pos[e] + 1) <= R[i]);
			// if (lf && rg) {
				// res = 1;
				// break;
			// }
			// if (!lf) r = m - 1;
			// else l = m + 1;
		// }
		ans[i] = res;
	}
	return ans;
}

컴파일 시 표준 에러 (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:42:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |  dfs(root);
      |  ~~~^~~~~~

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