oj.uz

Submission #302805

# Submission time Handle Problem Language Result Execution time Memory
302805 2020-09-19T08:41:36 Z BlancaHM Regions (IOI09_regions) C++14
1 / 100
 8000 ms 21344 KB 
#include <iostream>
#include <fstream>
#include <cfloat>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#include <cmath>
#include <climits>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<string> vs;
#define fir first
#define sec second
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define len(v) ((int)v.size())
#define all(v) v.begin(), v.end()

vi country;
vvi G;
int N, R, e1, e2, ans;

int dfs(int S) {
	int cur = 0;
	for (auto v: G[S]) {
		cur += dfs(v);
		if (country[v] == e2) cur++;
	}
	if (country[S] == e1) ans += cur;
	return cur;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int Q, cn, sup;
	cin >> N >> R >> Q;
	G.assign(N, vi());
	country = vi(N);
	cin >> cn;
	country[0] = cn;
	map<pii, int> past;
	for (int i = 1; i < N; i++) {
		cin >> sup >> cn;
		G[sup-1].push_back(i);
		country[i] = cn;
	}
	while(Q--) {
		cin >> e1 >> e2;
		if (past.find(mp(e1, e2)) != past.end()) {
			cout << past[mp(e1, e2)] << "\n";
			continue;
		}
		ans = 0;
		dfs(0);
		cout << ans << "\n";
		past[mp(e1, e2)] = ans;
		cout.flush();
	}
	return 0;
}

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 384 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 384 KB Time limit exceeded (wall clock)
7 Execution timed out 10 ms 384 KB Time limit exceeded (wall clock)
8 Execution timed out 15 ms 640 KB Time limit exceeded (wall clock)
9 Execution timed out 35 ms 896 KB Time limit exceeded (wall clock)
10 Execution timed out 76 ms 896 KB Time limit exceeded (wall clock)
11 Execution timed out 31 ms 1280 KB Time limit exceeded (wall clock)
12 Execution timed out 102 ms 1792 KB Time limit exceeded (wall clock)
13 Execution timed out 353 ms 1656 KB Time limit exceeded (wall clock)
14 Execution timed out 290 ms 2040 KB Time limit exceeded (wall clock)
15 Execution timed out 322 ms 4636 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 61 ms 5368 KB Time limit exceeded (wall clock)
2 Execution timed out 52 ms 4216 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 7288 KB Time limit exceeded (wall clock)
4 Execution timed out 6483 ms 2972 KB Time limit exceeded (wall clock)
5 Execution timed out 1069 ms 4216 KB Time limit exceeded (wall clock)
6 Execution timed out 81 ms 3328 KB Time limit exceeded (wall clock)
7 Execution timed out 103 ms 4224 KB Time limit exceeded (wall clock)
8 Execution timed out 699 ms 9464 KB Time limit exceeded (wall clock)
9 Execution timed out 8039 ms 9852 KB Time limit exceeded
10 Execution timed out 6744 ms 15128 KB Time limit exceeded (wall clock)
11 Execution timed out 8023 ms 9592 KB Time limit exceeded
12 Execution timed out 8042 ms 11640 KB Time limit exceeded
13 Execution timed out 8025 ms 11968 KB Time limit exceeded
14 Execution timed out 8029 ms 11468 KB Time limit exceeded
15 Execution timed out 8016 ms 15956 KB Time limit exceeded
16 Execution timed out 4685 ms 21344 KB Time limit exceeded (wall clock)
17 Execution timed out 952 ms 20144 KB Time limit exceeded (wall clock)