oj.uz

Submission #247452

# Submission time Handle Problem Language Result Execution time Memory
247452 2020-07-11T12:17:51 Z mode149256 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 24568 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];
}

vi curr;



void hld(int x, bool keep) { // true if keep
	int bigChild = -1;

	for (auto u : edges[x]) {
		if (bigChild == -1 or sz[u] > sz[bigChild])
			bigChild = u;
	}

	for (auto u : edges[x]) {
		if (bigChild != u)
			hld(u, false);
	}

	if (bigChild != -1)
		hld(bigChild, true);

	for (auto u : edges[x]) {
		if (bigChild != u) {
			for (int i = timeIn[u]; i < timeOut[u]; ++i)
			{
				curr[kas[atgal[i]]]++;
			}
		}
	}

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

	if (keep) return;

	for (int i = timeIn[x]; i < timeOut[x]; ++i)
	{
		curr[kas[atgal[i]]]--;
	}
}

void precompute() {
	curr = vi(R + 1, 0);
	hld(1, 1);
}

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 9 ms 5992 KB Output is correct
2 Correct 8 ms 6016 KB Output is correct
3 Correct 10 ms 6016 KB Output is correct
4 Correct 11 ms 6016 KB Output is correct
5 Correct 15 ms 6144 KB Output is correct
6 Correct 18 ms 6144 KB Output is correct
7 Correct 40 ms 6144 KB Output is correct
8 Correct 46 ms 6144 KB Output is correct
9 Correct 58 ms 6780 KB Output is correct
10 Correct 106 ms 6528 KB Output is correct
11 Correct 131 ms 7040 KB Output is correct
12 Correct 125 ms 7544 KB Output is correct
13 Correct 206 ms 7144 KB Output is correct
14 Correct 218 ms 7680 KB Output is correct
15 Correct 248 ms 11560 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 11360 KB Output is correct
2 Correct 1068 ms 9836 KB Output is correct
3 Correct 1522 ms 13852 KB Output is correct
4 Correct 309 ms 7808 KB Output is correct
5 Correct 442 ms 9088 KB Output is correct
6 Execution timed out 8070 ms 9088 KB Time limit exceeded
7 Correct 6037 ms 10220 KB Output is correct
8 Correct 3501 ms 14404 KB Output is correct
9 Correct 5702 ms 15584 KB Output is correct
10 Execution timed out 8051 ms 19704 KB Time limit exceeded
11 Execution timed out 8039 ms 15864 KB Time limit exceeded
12 Execution timed out 8009 ms 17432 KB Time limit exceeded
13 Execution timed out 8026 ms 17272 KB Time limit exceeded
14 Execution timed out 8077 ms 17276 KB Time limit exceeded
15 Execution timed out 8025 ms 20600 KB Time limit exceeded
16 Execution timed out 8005 ms 24568 KB Time limit exceeded
17 Execution timed out 8010 ms 23548 KB Time limit exceeded