oj.uz

Submission #362636

# Submission time Handle Problem Language Result Execution time Memory
362636 2021-02-03T18:45:00 Z NachoLibre Werewolf (IOI18_werewolf) C++17
100 / 100
 1205 ms 113988 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "werewolf.h"
#else
#endif

inline int Max(int a, int b) {
	return (a > b ? a : b);
}

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);
	}
};

struct doo {
	const int n;
	ovo *rt;
	doo(int _n) : n(_n), rt(NULL) {}

	static int si, vl;
	static 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();
	}

	static int sl, sr;
	static 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));
	}

	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);
	}
};
int doo::si = 0, doo::vl = 0, doo::sl = 0, doo::sr = 0;

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

werewolf.cpp: In function 'vint check_validity(int, vint, vint, vint, vint, vint, vint)':
werewolf.cpp:184: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]
  184 |   for(int j = 0; j < ve[i].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 17 ms 15852 KB Output is correct
11 Correct 17 ms 15852 KB Output is correct
12 Correct 17 ms 15852 KB Output is correct
13 Correct 17 ms 15852 KB Output is correct
14 Correct 17 ms 15852 KB Output is correct
15 Correct 19 ms 15980 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 98156 KB Output is correct
2 Correct 955 ms 106288 KB Output is correct
3 Correct 844 ms 106348 KB Output is correct
4 Correct 767 ms 106220 KB Output is correct
5 Correct 781 ms 106092 KB Output is correct
6 Correct 829 ms 106092 KB Output is correct
7 Correct 737 ms 105364 KB Output is correct
8 Correct 888 ms 106448 KB Output is correct
9 Correct 767 ms 106196 KB Output is correct
10 Correct 621 ms 105148 KB Output is correct
11 Correct 619 ms 105960 KB Output is correct
12 Correct 646 ms 105696 KB Output is correct
13 Correct 925 ms 109416 KB Output is correct
14 Correct 908 ms 109040 KB Output is correct
15 Correct 922 ms 109052 KB Output is correct
16 Correct 906 ms 108956 KB Output is correct
17 Correct 718 ms 105288 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 11 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 17 ms 15852 KB Output is correct
11 Correct 17 ms 15852 KB Output is correct
12 Correct 17 ms 15852 KB Output is correct
13 Correct 17 ms 15852 KB Output is correct
14 Correct 17 ms 15852 KB Output is correct
15 Correct 19 ms 15980 KB Output is correct
16 Correct 809 ms 98156 KB Output is correct
17 Correct 955 ms 106288 KB Output is correct
18 Correct 844 ms 106348 KB Output is correct
19 Correct 767 ms 106220 KB Output is correct
20 Correct 781 ms 106092 KB Output is correct
21 Correct 829 ms 106092 KB Output is correct
22 Correct 737 ms 105364 KB Output is correct
23 Correct 888 ms 106448 KB Output is correct
24 Correct 767 ms 106196 KB Output is correct
25 Correct 621 ms 105148 KB Output is correct
26 Correct 619 ms 105960 KB Output is correct
27 Correct 646 ms 105696 KB Output is correct
28 Correct 925 ms 109416 KB Output is correct
29 Correct 908 ms 109040 KB Output is correct
30 Correct 922 ms 109052 KB Output is correct
31 Correct 906 ms 108956 KB Output is correct
32 Correct 718 ms 105288 KB Output is correct
33 Correct 1072 ms 106144 KB Output is correct
34 Correct 357 ms 50468 KB Output is correct
35 Correct 1202 ms 107116 KB Output is correct
36 Correct 996 ms 106604 KB Output is correct
37 Correct 1154 ms 106540 KB Output is correct
38 Correct 1031 ms 106852 KB Output is correct
39 Correct 1014 ms 110044 KB Output is correct
40 Correct 1111 ms 113972 KB Output is correct
41 Correct 901 ms 105448 KB Output is correct
42 Correct 711 ms 105740 KB Output is correct
43 Correct 1205 ms 110596 KB Output is correct
44 Correct 998 ms 106560 KB Output is correct
45 Correct 809 ms 110584 KB Output is correct
46 Correct 832 ms 110156 KB Output is correct
47 Correct 895 ms 109344 KB Output is correct
48 Correct 951 ms 108920 KB Output is correct
49 Correct 900 ms 109184 KB Output is correct
50 Correct 876 ms 109100 KB Output is correct
51 Correct 955 ms 113892 KB Output is correct
52 Correct 975 ms 113988 KB Output is correct