제출 #413631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413631		_fractal	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1257 ms	106064 KiB

werewolf

#include "werewolf.h"
#include <iostream>
using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 200200;

int n;
vector<int> g[N];
vector<pair<pair<int, int>, pair<int, int>>> p[N];

struct tree {
	int t[N << 2];

	void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
		if (tl == tr)
			return t[v] = val, void();
		int tm = tl + tr >> 1;
		if (pos <= tm)
			upd(pos, val, v * 2, tl, tm);
		else
			upd(pos, val, v * 2 + 1, tm + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}

	int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
		if (l <= tl && tr <= r)
			return t[v];
		if (r < tl || tr < l)
			return 0;
		int tm = tl + tr >> 1;
		return max(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
	}
} t;

struct tree_dsu {
	int p[N], sz[N], root, up[20][N], LG = 18;
	int tin[N], tout[N], tick, pos[N];
	vector<int> h[N];

	int mxup(int v, int k) {
		if (v == k) return v;
		for (int i = LG; i >= 0; --i) {
			int u = up[i][v];
			if (u >= 0 && u >= k)
				v = u;
		}
		return v;
	}

	int mnup(int v, int k) {
		if (v == k) return v;
		for (int i = LG; i >= 0; --i) {
			int u = up[i][v];
			if (u >= 0 && u <= k)
				v = u;
		}
		return v;
	}

	void dfs(int v, int p = -1) {
		tin[v] = ++tick;
		pos[tick] = v;
		up[0][v] = p;
		for (int i = 1; i <= LG; ++i) {
			if (up[i - 1][v] == -1)
				up[i][v] = -1;
			else
				up[i][v] = up[i - 1][up[i - 1][v]];
		}
		for (auto to : h[v])
			dfs(to, v);
		tout[v] = tick;
	}

	void init(int n) {
		for (int i = 0; i < n; ++i)
			p[i] = i, sz[i] = 1, h[i].clear();
	}

	int get(int v) {
		return p[v] = (v == p[v] ? v : get(p[v]));
	}
	
	void unite(int v, int u) {
		if ((v = get(v)) == (u = get(u)))
			return;
		h[v].pb(u);
		root = v;
		sz[v] += sz[u];
		p[u] = v;
	}
} ds, sd;

vector<int> check_validity(int _n, vector<int> U, vector<int> V, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int q = S.size();
	int m = U.size();
	n = _n;
	int r;
	vector<int> ans(q, 0);
	ds.init(n);
	sd.init(n);
	for (int i = 0; i < m; ++i) {
		g[U[i]].pb(V[i]);
		g[V[i]].pb(U[i]);
	}
	for (int i = n - 1; i >= 0; --i) {
		for (auto to : g[i]) {
			if (to > i)
				ds.unite(i, to);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (auto to : g[i]) {
			if (to < i)
				sd.unite(i, to);
		}
	}
	ds.dfs(ds.root);
	sd.dfs(sd.root);
	for (int i = 0, l1, r1, l2, r2, v, u; i < q; ++i) {
		v = ds.mxup(S[i], L[i]);
		u = sd.mnup(E[i], R[i]);
		l1 = ds.tin[v], r1 = ds.tout[v];
		l2 = sd.tin[u], r2 = sd.tout[u];
		p[r1].pb({{i, l1}, {l2, r2}});
	}
	for (int i = 1; i <= n; ++i) {
		t.upd(sd.tin[ds.pos[i]], i);
		for (auto it : p[i]) {
			if (t.get(it.S.F, it.S.S) >= it.F.S)
				ans[it.F.F] = 1;
			else
				ans[it.F.F] = 0;
		}
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In member function 'void tree::upd(int, int, int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
werewolf.cpp: In member function 'int tree::get(int, int, int, int, int)':
werewolf.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
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:102:6: warning: unused variable 'r' [-Wunused-variable]
  102 |  int r;
      |      ^

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