oj.uz

Submission #247457

# Submission time Handle Problem Language Result Execution time Memory
247457 2020-07-11T12:31:51 Z mode149256 Regions (IOI09_regions) C++14
25 / 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];
}


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;
	} else {
		assert(false);
	}

	// 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 14 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 14 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 14 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 15 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 15 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 15 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 12288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 12928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 18 ms 13184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 13696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 24 ms 14720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 23 ms 14080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 25 ms 15360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 30 ms 19448 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 21368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 43 ms 19368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 47 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 363 ms 7808 KB Output is correct
5 Correct 462 ms 9216 KB Output is correct
6 Execution timed out 8007 ms 9088 KB Time limit exceeded
7 Correct 6404 ms 10232 KB Output is correct
8 Correct 3545 ms 14328 KB Output is correct
9 Correct 5926 ms 15480 KB Output is correct
10 Execution timed out 8055 ms 19704 KB Time limit exceeded
11 Execution timed out 8006 ms 15864 KB Time limit exceeded
12 Execution timed out 8045 ms 17400 KB Time limit exceeded
13 Execution timed out 8082 ms 17272 KB Time limit exceeded
14 Execution timed out 8076 ms 17272 KB Time limit exceeded
15 Execution timed out 8077 ms 20600 KB Time limit exceeded
16 Execution timed out 8054 ms 24568 KB Time limit exceeded
17 Execution timed out 8098 ms 23572 KB Time limit exceeded