Submission #362327

#	Time	Username	Problem	Language	Result	Execution time	Memory
362327		NachoLibre	Werewolf (IOI18_werewolf)	C++17	100 / 100	1233 ms	114408 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "werewolf.h"
#else
#endif

struct ovo {
	ovo *l, *r;
	int m;
	ovo() {
		l = r = NULL;
		m = -1;
	}

	void P() {
		if(l == NULL) l = new ovo();
		if(r == NULL) r = new ovo();
		m = max(l->m, r->m);
	}
};

int si, vl;
void _G(int l, int r, ovo *&t) {
	if(t == NULL) t = new ovo();
	if(l == r) {
		t->m = vl;
		return;
	}
	int m = (l + r) / 2;
	if(m >= si) _G(l, m, t->l);
	else _G(m + 1, r, t->r);
	t->P();
}

int sl, sr;
int _S(int l, int r, ovo *&t) {
	if(l > sr || r < sl || t == NULL) return -1;
	if(l >= sl && r <= sr) return t->m;
	int m = (l + r) / 2;
	return max(_S(l, m, t->l), _S(m + 1, r, t->r));
}

struct doo {
	const int n;
	ovo *rt;
	doo(int _n) : n(_n), rt(NULL) {}
	void set(int _si, int _vl) {
		si = _si;
		vl = _vl;
		_G(1, n, rt);
	}

	int max(int _sl, int _sr) {
		sl = _sl; sr = _sr;
		return _S(1, n, rt);
	}
};

const int N = 200005, L = 20;
vint v[N], xs[2][N];
int ups[2][N], up[2][N][L], rm, io[2][N][2];

int P(int x) {
	return (ups[rm][x] == -1 ? x : ups[rm][x] = P(ups[rm][x]));
}

void U(int x, int y) {
	if((rm && y < x) || (!rm && y > x) || P(x) == P(y)) return;
	up[rm][P(y)][0] = P(x);
	xs[rm][P(x)].push_back(P(y));
	ups[rm][P(y)] = P(x);
}

void sgs(int x) {
	for(int i = 1; i < L; ++i) {
		if(up[rm][x][i - 1] == -1) break;
		up[rm][x][i] = up[rm][up[rm][x][i - 1]][i - 1];
	}
	io[rm][x][1] = io[rm][x][0];
	for(int i = 0; i < sz(xs[rm][x]); ++i) {
		io[rm][xs[rm][x][i]][0] = io[rm][x][1] + 1;
		sgs(xs[rm][x][i]);
		io[rm][x][1] = io[rm][xs[rm][x][i]][1];
	}
}

int W(int x, int y, int z) {
	for(int i = L - 1; i >= 0; --i) {
		if(up[z][x][i] == -1) continue;
		if((z && up[z][x][i] >= y) || (!z && up[z][x][i] <= y)) {
			x = up[z][x][i];
		}
	}
	return x;
}
vint check_validity(int n, vint x, vint y, vint s, vint e, vint l, vint r) {
	//  //  //  //  //  //  //  //
	int m = sz(x);
	int q = sz(s);
	vint dr(q);
	//  //  //  //  //  //  //  //
	for(int i = 0; i < m; ++i) {
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	//  //  //  //  //  //  //  //
	for(int i = 0; i < n; ++i) {
		ups[0][i] = ups[1][i] = -1;
		for(int j = 0; j < L; ++j) {
			up[0][i][j] = up[1][i][j] = -1;
		}
	}
	//  //  //  //  //  //  //  //
	rm = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < sz(v[i]); ++j) {
			U(i, v[i][j]);
		}
	}
	rm = 1;
	for(int i = n - 1; i >= 0; --i) {
		for(int j = 0; j < sz(v[i]); ++j) {
			U(i, v[i][j]);
		}
	}
	//  //  //  //  //  //  //  //
	for(rm = 0; rm < 2; ++rm) {
		int bg = -1;
		for(int i = 0; i < n; ++i) {
			if(up[rm][i][0] == -1) {
				io[rm][i][0] = (bg == -1 ? 1 : io[rm][bg][1] + 1);
				sgs(i);
				bg = i;
			}
		}
	}
	//  //  //  //  //  //  //  //
	#ifdef wambulex
	int rml = 1;
	cout << "|-[ up ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		cout << up[rml][i][0] << " ";
	}
	cout << endl << "________" << endl;
	cout << "|-[ in ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		cout << io[rml][i][0] << " ";
	}
	cout << endl << "________" << endl;
	cout << "|-[ out ]-|" << endl;
	for(int i = 0; i < n; ++i) {
		cout << io[rml][i][1] << " ";
	}
	cout << endl << "________" << endl;
	#endif
	//  //  //  //  //  //  //  //
	vector<pair<pair<int, int>, pair<int, int>>> ve[n + 1];
	for(int i = 0; i < q; ++i) {
		int x = W(s[i], l[i], 1);
		int y = W(e[i], r[i], 0);
		int l0 = io[0][y][0];
		int r0 = io[0][y][1];
		int l1 = io[1][x][0];
		int r1 = io[1][x][1];
		ve[r0].push_back({{l1, r1}, {l0, i}});
	}
	//  //  //  //  //  //  //  //
	int a[n + 1];
	for(int i = 0; i < n; ++i) {
		a[io[0][i][0]] = i;
	}
	//  //  //  //  //  //  //  //
	doo st(n);
	for(int i = 1; i <= n; ++i) {
		st.set(io[1][a[i]][0], i);
		for(int j = 0; j < ve[i].size(); ++j) {
			if(st.max(ve[i][j].first.first, ve[i][j].first.second) >= ve[i][j].second.first) {
				dr[ve[i][j].second.second] = 1;
			}
		}
	}
	//  //  //  //  //  //  //  //
	#ifdef wambule
	#endif
	//  //  //  //  //  //  //  //
	return dr;
	//  //  //  //  //  //  //  //
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int ty = 3;
	if(ty == 0) {
		int n;
		cin >> n;
		doo st(n);
		while(7) {
			int x, y, z;
			cin >> x >> y >> z;
			if(x) st.set(y, z);
			else cout << st.max(y, z) << endl;
		}
	} else if(ty == 1) {
		//  //  //  //  //  //  //  //
		string s;
		char c;
		while(8) {
			cin >> c;
			if(c == '.') break;
			if(c == '[') c = '{';
			if(c == ']') c = '}';
			s += c;
			if(c == ',') s += ' ';
		}
		cout << endl << s << endl;
		//  //  //  //  //  //  //  //
	} else {
		//  //  //  //  //  //  //  //
		vint v;
		v = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
			              {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
		for(int i = 0; i < v.size(); ++i) {
			cout << v[i] << " ";
		}
		cout << endl;
		//  //  //  //  //  //  //  //
	}
	return 0;
}
#endif

Compilation message (stderr)

werewolf.cpp: In function 'vint check_validity(int, vint, vint, vint, vint, vint, vint)':
werewolf.cpp:179:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   for(int j = 0; j < ve[i].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~

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