oj.uz

Submission #247462

# Submission time Handle Problem Language Result Execution time Memory
247462 2020-07-11T12:44:43 Z mode149256 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 27128 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);

	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 8 ms 6064 KB Output is correct
2 Correct 8 ms 6016 KB Output is correct
3 Correct 11 ms 6016 KB Output is correct
4 Correct 10 ms 6016 KB Output is correct
5 Correct 15 ms 6144 KB Output is correct
6 Correct 24 ms 6144 KB Output is correct
7 Correct 37 ms 6144 KB Output is correct
8 Correct 48 ms 6144 KB Output is correct
9 Correct 64 ms 6656 KB Output is correct
10 Correct 133 ms 6776 KB Output is correct
11 Correct 154 ms 6912 KB Output is correct
12 Correct 215 ms 7552 KB Output is correct
13 Correct 269 ms 7168 KB Output is correct
14 Correct 223 ms 7808 KB Output is correct
15 Correct 277 ms 10368 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 11344 KB Output is correct
2 Correct 1224 ms 10084 KB Output is correct
3 Correct 1527 ms 13104 KB Output is correct
4 Correct 278 ms 7808 KB Output is correct
5 Correct 441 ms 9532 KB Output is correct
6 Execution timed out 8029 ms 9088 KB Time limit exceeded
7 Correct 5855 ms 10284 KB Output is correct
8 Correct 3488 ms 15388 KB Output is correct
9 Correct 5493 ms 15832 KB Output is correct
10 Execution timed out 8079 ms 20856 KB Time limit exceeded
11 Execution timed out 8023 ms 15864 KB Time limit exceeded
12 Execution timed out 8042 ms 17400 KB Time limit exceeded
13 Execution timed out 8026 ms 17528 KB Time limit exceeded
14 Execution timed out 8086 ms 17272 KB Time limit exceeded
15 Execution timed out 8077 ms 21624 KB Time limit exceeded
16 Execution timed out 8067 ms 27128 KB Time limit exceeded
17 Execution timed out 8048 ms 25804 KB Time limit exceeded