oj.uz

Submission #247470

# Submission time Handle Problem Language Result Execution time Memory
247470 2020-07-11T12:48:13 Z mode149256 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 105168 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;
vii ats(501, vi(501, 0));
int piv = 0;

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

bool anc(int a, int b) { // a is ancestor of b
	return timeIn[a] <= timeIn[b] && timeOut[b] <= timeOut[a];
}


void dfs(int x, vi &curr) {
	for (auto u : edges[x]) {
		vi naujas(R + 1, 0);
		dfs(u, naujas);
		for (int i = 1; i <= R; ++i)
			curr[i] += naujas[i];

	}

	// have curr
	for (int i = 1; i <= R; ++i)
		ats[kas[x]][i] += curr[i];

	curr[kas[x]]++;
}

struct FENWICK {
	vi A;
	int N;
	FENWICK(int n): N(n) {
		A.resize(n + 1, 0);
	}
	void add(int i, int x) {
		for (; i <= N; i += (i) & (-i))
			A[i] += x;
	}
	int getQ(int i) {
		int get = 0;
		for (; i > 0; i -= (i) & (-i))
			get += A[i];
		return get;
	}
};

void precompute() {
	// vi pivas(R + 1, 0);
	// dfs(1, pivas);

	vector<FENWICK> fenvikai(R + 1, FENWICK(N + 1));

	for (int r = 1; r <= R; ++r)
	{
		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
			ats[kas[c]][r] += sum[timeOut[c] - 1] - (timeIn[c] ? sum[timeIn[c] - 1] : 0);
		}
	}
}

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

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

	if (R > 500) {
		for (int i = 0; i < Q; ++i)
		{
			int r1, r2;
			cin >> r1 >> r2;
			int ans = 0;
			for (auto a : kokie[r1]) {
				for (auto b : kokie[r2]) {
					ans += anc(a, b);
				}
			}
			cout << ans << endl;
		}

		return 0;
	}

	// R <= 500

	precompute();

	for (int i = 0; i < Q; ++i)
	{
		int r1, r2;
		cin >> r1 >> r2;
		cout << ats[r1][r2] << 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 7 ms 6016 KB Output is correct
2 Correct 8 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 14 ms 6016 KB Output is correct
5 Correct 15 ms 6144 KB Output is correct
6 Correct 33 ms 6912 KB Output is correct
7 Correct 43 ms 7040 KB Output is correct
8 Correct 52 ms 7680 KB Output is correct
9 Correct 85 ms 12672 KB Output is correct
10 Correct 152 ms 23200 KB Output is correct
11 Correct 156 ms 22912 KB Output is correct
12 Correct 244 ms 43000 KB Output is correct
13 Correct 295 ms 39160 KB Output is correct
14 Correct 267 ms 31352 KB Output is correct
15 Correct 334 ms 49112 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 70776 KB Output is correct
2 Correct 1346 ms 80060 KB Output is correct
3 Correct 1897 ms 105168 KB Output is correct
4 Correct 339 ms 7800 KB Output is correct
5 Correct 479 ms 9564 KB Output is correct
6 Execution timed out 8002 ms 9080 KB Time limit exceeded
7 Correct 6054 ms 10280 KB Output is correct
8 Correct 3406 ms 15224 KB Output is correct
9 Correct 5473 ms 15828 KB Output is correct
10 Execution timed out 8055 ms 20856 KB Time limit exceeded
11 Execution timed out 8048 ms 15864 KB Time limit exceeded
12 Execution timed out 8016 ms 17528 KB Time limit exceeded
13 Execution timed out 8018 ms 17528 KB Time limit exceeded
14 Execution timed out 8020 ms 17400 KB Time limit exceeded
15 Execution timed out 8058 ms 21624 KB Time limit exceeded
16 Execution timed out 8045 ms 27256 KB Time limit exceeded
17 Execution timed out 8099 ms 25976 KB Time limit exceeded