oj.uz

Submission #248579

# Submission time Handle Problem Language Result Execution time Memory
248579 2020-07-12T19:06:24 Z mode149256 Regions (IOI09_regions) C++14
100 / 100
 3274 ms 40312 KB 
/*input
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 200101;

int N, R, Q;
vi edges[MX];
vi kas;
vii kokie;

vi timeIn;
vi timeOut;
vi atgal;
vi sz;
vi indeks;
vii ats;
vii revAts;
int piv = 0;
int sqr;

int dfs(int x) {
	atgal[piv] = x;
	timeIn[x] = piv++;
	sz[x] = 1;
	for (auto u : edges[x])
		sz[x] += dfs(u);

	timeOut[x] = piv;
	return sz[x];
}

void precompute() {
	piv = 0;
	for (int r = 1; r <= R; ++r)
	{
		if ((int)kokie[r].size() < sqr) continue;

		indeks[r] = piv;
		ats.emplace_back(vi(R + 1, 0));
		revAts.emplace_back(vi(R + 1, 0));

		vi sum(N + 1, 0);
		for (int i = 0; i < N; ++i)
			sum[i] = (kas[atgal[i]] == r) + (i ? sum[i - 1] : 0);

		for (int i = 0; i < N; ++i)
		{
			int c = atgal[i]; // node
			revAts[piv][kas[c]] += sum[timeOut[c] - 1] - (timeIn[c] ? sum[timeIn[c] - 1] : 0);
		}

		vi plius(N + 1, 0);
		for (auto u : kokie[r]) {
			plius[u]++;
			plius[timeOut[atgal[u]]]--;
		}

		for (int i = 0; i < N; ++i)
		{
			plius[i] += (i ? plius[i - 1] : 0);
			ats[piv][kas[atgal[i]]] += plius[i];
		}

		piv++;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> R >> Q;
	kas.resize(N + 1);
	kokie.resize(R + 1);
	timeIn.resize(N + 1);
	timeOut.resize(N + 1);
	sz.resize(N + 1);
	atgal.resize(N + 1);
	indeks.resize(N + 1);

	sqr = (int)sqrt(N);

	cin >> kas[1];
	kokie[kas[1]].emplace_back(1);

	for (int i = 2; i <= N; ++i)
	{
		int a; cin >> a >> kas[i];
		edges[a].push_back(i);
		kokie[kas[i]].emplace_back(i);
	}

	dfs(1);

	for (auto && vec : kokie) {
		for (auto && u : vec)
			u = timeIn[u];

		sort(vec.begin(), vec.end());
	}
	precompute();

	for (int i = 0; i < Q; ++i)
	{
		int r1, r2;
		cin >> r1 >> r2;
		int cnt = 0;

		if ((int)kokie[r1].size() >= sqr) {
			cout << ats[indeks[r1]][r2] << endl;
		} else if ((int)kokie[r2].size() >= sqr) {
			cout << revAts[indeks[r2]][r1] << endl;
		} else {
			stack<int> uzdaryt;

			int j1 = 0;

			int c = 0;
			for (auto u : kokie[r2]) {
				while (uzdaryt.size() and uzdaryt.top() <= u) {
					c--;
					uzdaryt.pop();
				}
				while (j1 < (int)kokie[r1].size() and kokie[r1][j1] <= u) {
					uzdaryt.push(timeOut[atgal[ kokie[r1][j1] ]]);
					c++;
					j1++;
					while (uzdaryt.size() and uzdaryt.top() <= u) {
						c--;
						uzdaryt.pop();
					}
				}

				cnt += c;
			}

			cout << cnt << endl;
		}
	}
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 10 ms 5120 KB Output is correct
6 Correct 17 ms 5120 KB Output is correct
7 Correct 29 ms 5120 KB Output is correct
8 Correct 35 ms 5120 KB Output is correct
9 Correct 61 ms 5504 KB Output is correct
10 Correct 73 ms 5632 KB Output is correct
11 Correct 87 ms 5888 KB Output is correct
12 Correct 125 ms 6400 KB Output is correct
13 Correct 193 ms 6144 KB Output is correct
14 Correct 201 ms 7040 KB Output is correct
15 Correct 226 ms 9216 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 10588 KB Output is correct
2 Correct 1184 ms 9724 KB Output is correct
3 Correct 1668 ms 12288 KB Output is correct
4 Correct 255 ms 6912 KB Output is correct
5 Correct 352 ms 8440 KB Output is correct
6 Correct 523 ms 11992 KB Output is correct
7 Correct 833 ms 13896 KB Output is correct
8 Correct 945 ms 22392 KB Output is correct
9 Correct 1962 ms 15160 KB Output is correct
10 Correct 2167 ms 40312 KB Output is correct
11 Correct 3274 ms 15648 KB Output is correct
12 Correct 1234 ms 18728 KB Output is correct
13 Correct 1786 ms 18728 KB Output is correct
14 Correct 1790 ms 22016 KB Output is correct
15 Correct 2403 ms 22360 KB Output is correct
16 Correct 2926 ms 26200 KB Output is correct
17 Correct 2632 ms 28520 KB Output is correct