oj.uz

Submission #247455

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

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

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 8 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 11 ms 6016 KB Output is correct
5 Correct 14 ms 6016 KB Output is correct
6 Correct 35 ms 6888 KB Output is correct
7 Correct 32 ms 6144 KB Output is correct
8 Correct 48 ms 6404 KB Output is correct
9 Correct 83 ms 12800 KB Output is correct
10 Correct 107 ms 6912 KB Output is correct
11 Correct 93 ms 7612 KB Output is correct
12 Correct 229 ms 15660 KB Output is correct
13 Correct 192 ms 7292 KB Output is correct
14 Correct 211 ms 7968 KB Output is correct
15 Correct 273 ms 50944 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 23672 KB Output is correct
2 Correct 1092 ms 11588 KB Output is correct
3 Correct 1725 ms 51028 KB Output is correct
4 Correct 350 ms 7808 KB Output is correct
5 Correct 483 ms 9196 KB Output is correct
6 Execution timed out 8058 ms 9088 KB Time limit exceeded
7 Correct 5982 ms 10240 KB Output is correct
8 Correct 3408 ms 14404 KB Output is correct
9 Correct 5941 ms 15584 KB Output is correct
10 Execution timed out 8064 ms 19704 KB Time limit exceeded
11 Execution timed out 8016 ms 15864 KB Time limit exceeded
12 Execution timed out 8006 ms 17272 KB Time limit exceeded
13 Execution timed out 8077 ms 17272 KB Time limit exceeded
14 Execution timed out 8003 ms 17272 KB Time limit exceeded
15 Execution timed out 8031 ms 20704 KB Time limit exceeded
16 Execution timed out 8086 ms 24568 KB Time limit exceeded
17 Execution timed out 8045 ms 23520 KB Time limit exceeded