oj.uz

Submission #531787

# Submission time Handle Problem Language Result Execution time Memory
531787 2022-03-01T13:47:32 Z akhan42 Regions (IOI09_regions) C++17
30 / 100
 1410 ms 131072 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 200 * 1000 + 10;
const int S = 500;
int n, R, Q;
vi gr[MX];
int e2r[MX];
vi r2es[MX];
int pc[S][MX];
int ct[MX];
vi regions;


bool cmp_reg(int r1, int r2) {
	return sz(r2es[r1]) > sz(r2es[r2]);
}


void dfs(int node = 0) {
	forn(i, min(R, S)) {
		int r = regions[i];
		pc[r][e2r[node]] += ct[r];
	}

	ct[e2r[node]] += 1;

	for(int nb: gr[node]) {
		dfs(nb);
	}

	ct[e2r[node]] -= 1;
}


void solve() {
	cin >> n >> R >> Q;

	forn(i, n) {
		int r, p;
		if(i == 0) {
			cin >> r;
		} else {
			cin >> p >> r;
			p -= 1;
			gr[p].pb(i);
		}
		r--;
		e2r[i] = r;
		r2es[r].pb(i);
	}

	forn(i, R)
		regions.pb(i);

//	sort(all(regions), cmp_reg);

	dfs();

	forn(_, Q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;

		cout << pc[r1][r2] << endl;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("haybales.in", "r", stdin);
//	freopen("haybales.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9672 KB Output is correct
2 Correct 5 ms 9672 KB Output is correct
3 Correct 6 ms 9800 KB Output is correct
4 Correct 9 ms 9832 KB Output is correct
5 Correct 12 ms 10056 KB Output is correct
6 Correct 21 ms 11372 KB Output is correct
7 Correct 31 ms 10696 KB Output is correct
8 Correct 35 ms 10992 KB Output is correct
9 Correct 64 ms 12176 KB Output is correct
10 Correct 102 ms 13000 KB Output is correct
11 Correct 103 ms 12104 KB Output is correct
12 Correct 197 ms 14024 KB Output is correct
13 Correct 187 ms 12616 KB Output is correct
14 Correct 186 ms 12128 KB Output is correct
15 Correct 192 ms 14744 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 14528 KB Output is correct
2 Correct 891 ms 13416 KB Output is correct
3 Correct 1213 ms 16648 KB Output is correct
4 Runtime error 153 ms 42880 KB Execution killed with signal 11
5 Runtime error 263 ms 50132 KB Execution killed with signal 11
6 Runtime error 298 ms 56960 KB Execution killed with signal 11
7 Runtime error 444 ms 70304 KB Execution killed with signal 11
8 Runtime error 592 ms 79608 KB Execution killed with signal 11
9 Runtime error 950 ms 98576 KB Execution killed with signal 11
10 Runtime error 1147 ms 131072 KB Execution killed with signal 11
11 Runtime error 1291 ms 131072 KB Execution killed with signal 11
12 Runtime error 1199 ms 104540 KB Execution killed with signal 11
13 Runtime error 1204 ms 104912 KB Execution killed with signal 11
14 Runtime error 1256 ms 119988 KB Execution killed with signal 11
15 Runtime error 1278 ms 131072 KB Execution killed with signal 11
16 Runtime error 1410 ms 131072 KB Execution killed with signal 11
17 Runtime error 1207 ms 131072 KB Execution killed with signal 11