oj.uz

Submission #1109428

# Submission time Handle Problem Language Result Execution time Memory
1109428 2024-11-06T16:28:42 Z sano Regions (IOI09_regions) C++14
100 / 100
 6175 ms 31420 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<int, int>
#define NEK 2147483640
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

vec<vec<int>> g;
vec<int> eul1, eul2;
vec<vec<int>> odp;
vec<int> e;
vec<vec<int>> m;
int ti = 0;

void DFS(int x, int pr) {
	eul1[x] = ti; ti++; m[e[x]].push_back(eul1[x]);
	for (auto i : g[x]) {
		if (i == pr) continue;
		DFS(i, x);
	}
	eul2[x] = ti - 1;
	return;
}

bool zorad(vec<int>& a, vec<int>& b) {
	return a.size() > b.size();
}

void DFS2(int x, int pr, int k, int v = 0) {
	if (e[x] == k) v++;
	odp.back()[e[x]] += v;
	for (auto i : g[x]) {
		if (i == pr) continue;
		DFS2(i, x, k, v);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//ifstream cin("promote.in");
	//ofstream cout("promote.out");
	int n, r, q;
	cin >> n >> r >> q;
	vec<vec<int>> reg(r);
	g.resize(n); eul1.resize(n); eul2.resize(n);
	e.resize(n);
	cin >> e[0]; e[0]--;
	reg[e[0]].push_back(0);
	ffor(i, 1, n) {
		int x; cin >> x; x--;
		g[x].push_back(i);
		g[i].push_back(x);
		cin >> e[i]; e[i]--;
		reg[e[i]].push_back(i);
	}
	m.resize(r);
	DFS(0, -1);

	sort(reg.begin(), reg.end(), zorad);
	vec<int> s_n(r, -1);
	For(i, reg.size()) {
		if (reg[i].empty()) continue;
		s_n[e[reg[i][0]]] = i;
	}
	int odm = sqrt(n);
	vec<int> trol(r, 0);
	For(i, reg.size()) {
		if (reg[i].size() >= odm) {
			odp.push_back(trol);
			DFS2(0, -1, e[reg[i][0]]);
		}
	}
	For(i, m.size()) {
		sort(m[i].begin(), m[i].end());
	}
	For(i, q) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (s_n[r1] == -1) {
			cout << 0 << endl;
			continue;
		}
		if (s_n[r1] >= odp.size()) {
			int vys = 0;
			for (auto i : reg[s_n[r1]]) {
				int q1 = lower_bound(m[r2].begin(), m[r2].end(), eul1[i]) - m[r2].begin();
				int q2 = upper_bound(m[r2].begin(), m[r2].end(), eul2[i]) - m[r2].begin();
				vys += q2 - q1;
			}
			cout << vys << endl;
		}
		else {
			cout << odp[s_n[r1]][r2] << endl;
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:97:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if (reg[i].size() >= odm) {
      |       ~~~~~~~~~~~~~~^~~~~~
regions.cpp:111:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   if (s_n[r1] >= odp.size()) {

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 23 ms 336 KB Output is correct
7 Correct 53 ms 592 KB Output is correct
8 Correct 62 ms 592 KB Output is correct
9 Correct 91 ms 1104 KB Output is correct
10 Correct 163 ms 1104 KB Output is correct
11 Correct 207 ms 1616 KB Output is correct
12 Correct 254 ms 2128 KB Output is correct
13 Correct 304 ms 2440 KB Output is correct
14 Correct 426 ms 2932 KB Output is correct
15 Correct 442 ms 6200 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2594 ms 7220 KB Output is correct
2 Correct 3013 ms 6896 KB Output is correct
3 Correct 4320 ms 9588 KB Output is correct
4 Correct 538 ms 3280 KB Output is correct
5 Correct 680 ms 4896 KB Output is correct
6 Correct 1240 ms 7044 KB Output is correct
7 Correct 2181 ms 9076 KB Output is correct
8 Correct 1964 ms 17308 KB Output is correct
9 Correct 3737 ms 14664 KB Output is correct
10 Correct 4739 ms 31420 KB Output is correct
11 Correct 6175 ms 18804 KB Output is correct
12 Correct 2226 ms 16756 KB Output is correct
13 Correct 3098 ms 17764 KB Output is correct
14 Correct 3758 ms 19976 KB Output is correct
15 Correct 5182 ms 22836 KB Output is correct
16 Correct 5484 ms 30096 KB Output is correct
17 Correct 5218 ms 29668 KB Output is correct