Submission #896642

#	Time	Username	Problem	Language	Result	Execution time	Memory
896642		aykhn	Werewolf (IOI18_werewolf)	C++17	100 / 100	977 ms	339840 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

struct SegTree
{
	int sz = 1;
	vector<int> st;
	void init(int n)
	{
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, 0);
	}
	void add(int l, int r, int x, int ind)
	{
		if (l + 1 == r) 
		{
			st[x]++;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) add(l, mid, 2*x + 1, ind);
		else add(mid, r, 2*x + 2, ind);
		st[x] = st[2*x + 1] + st[2*x + 2];
	}
	int get(int l, int r, int x, int lx, int rx)
	{
		if (l >= rx || r <= lx) return 0;
		if (l >= lx && r <= rx) return st[x];
		int mid = (l + r) >> 1;
		return get(l, mid, 2*x + 1, lx, rx) + get(mid, r, 2*x + 2, lx, rx);
	}
};

const int MXN = 1e6 + 6;
const int LOG = 20;

int nh, nw;
vector<int> hum[MXN], wol[MXN];
int eh[MXN], ew[MXN];
int ph[LOG][MXN], pw[LOG][MXN];
int whenh[MXN], whenw[MXN];
array<int, 2> rh[MXN], rw[MXN];
int idh[MXN], idw[MXN], revh[MXN], revw[MXN];
int tim;
int ans[MXN];
vector<array<int, 3>> qin[MXN], qout[MXN];
SegTree st;

void reset()
{
	for (int i = 0; i < MXN; i++) 
	{
		eh[i] = ew[i] = -1;
		rh[i][0] = rw[i][0] = inf;
		rh[i][1] = rw[i][1] = -inf;
		wol[i].clear();
		hum[i].clear();
	}
}
int geth(int x)
{
	if (eh[x] < 0) return x;
	return eh[x] = geth(eh[x]);
}
void uniteh(int x, int y)
{
	int val = x;
	x = geth(x);
	y = geth(y);
	if (x == y) return;
	whenh[nh] = val;
	hum[nh].pb(x);
	hum[nh].pb(y);
	eh[nh] = eh[x] + eh[y];
	eh[x] = eh[y] = nh;
	nh++;
}
void dfsh(int a)
{
	if (hum[a].empty())
	{
		idh[a] = ++tim;
		revh[tim] = a;
		rh[a][0] = rh[a][1] = idh[a];
		return;
	}
	for (int v : hum[a])
	{
		ph[0][v] = a;
		dfsh(v);
		rh[a][0] = min(rh[a][0], rh[v][0]);
		rh[a][1] = max(rh[a][1], rh[v][1]);
	}
}
int getw(int x)
{
	if (ew[x] < 0) return x;
	return ew[x] = getw(ew[x]);
}
void unitew(int x, int y)
{
	int val = y;
	x = getw(x);
	y = getw(y);
	if (x == y) return;
	whenw[nw] = val;
	wol[nw].pb(x);
	wol[nw].pb(y);
	ew[nw] = ew[x] + ew[y];
	ew[x] = ew[y] = nw;
	nw++;
}
void dfsw(int a)
{
	if (wol[a].empty())
	{
		idw[a] = ++tim;
		revw[tim] = a;
		rw[a][0] = rw[a][1] = idw[a];
		return;
	}
	for (int v : wol[a])
	{
		pw[0][v] = a;
		dfsw(v);
		rw[a][0] = min(rw[a][0], rw[v][0]);
		rw[a][1] = max(rw[a][1], rw[v][1]);
	}
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) 
{
	reset();
	nh = nw = N;
	vector<array<int, 2>> edges;
	for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
	sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
	{
		return a[0] > b[0];
	});
	for (const array<int, 2> a : edges) uniteh(a[0], a[1]);
	sort(all(edges), [&](const array<int, 2> &a, const array<int, 2> &b)
	{
		return a[1] < b[1];
	});
	for (const array<int, 2> a : edges) unitew(a[0], a[1]);
	tim = -1;
	ph[0][nh - 1] = nh - 1;
	dfsh(nh - 1);
	tim = -1;
	pw[0][nw - 1] = nw - 1;
	dfsw(nw - 1);
	for (int i = 1; i < LOG; i++) for (int j = 0; j < nh; j++) ph[i][j] = ph[i - 1][ph[i - 1][j]], pw[i][j] = pw[i - 1][pw[i - 1][j]];
	int Q = S.size();
	for (int i = 0; i < Q; i++)
	{
		int u = S[i], v = E[i], l = L[i], r = R[i];
		for (int j = LOG - 1; j >= 0; j--)
		{
			if (whenh[ph[j][u]] >= l) u = ph[j][u];
			if (whenw[pw[j][v]] <= r) v = pw[j][v];
		}
		qin[rh[u][0]].pb({rw[v][0], rw[v][1], i});
		qout[rh[u][1]].pb({rw[v][0], rw[v][1], i});
	}
	st.init(nw);
	for (int i = 0; i < nh; i++)
	{
		for (const array<int, 3> a : qin[i]) ans[a[2]] = st.get(0, st.sz, 0, a[0], a[1] + 1);
		st.add(0, st.sz, 0, idw[revh[i]]);
		for (const array<int, 3> a : qout[i]) ans[a[2]] = (st.get(0, st.sz, 0, a[0], a[1] + 1) > ans[a[2]] ? 1 : 0);
	}
	vector<int> res;
	for (int i = 0; i < Q; i++) res.pb(ans[i]);
	return res;
}

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:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 0; i < X.size(); i++) edges.pb({min(X[i], Y[i]), max(X[i], Y[i])});
      |                  ~~^~~~~~~~~~

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