oj.uz

Submission #1109423

# Submission time Handle Problem Language Result Execution time Memory
1109423 2024-11-06T16:21:54 Z sano Regions (IOI09_regions) C++14
26 / 100
 4372 ms 54088 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()) {
		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;
		//}
		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:96:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |   if (reg[i].size() >= odm) {
      |       ~~~~~~~~~~~~~~^~~~~~
regions.cpp:109: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]
  109 |   if (s_n[r1] >= odp.size()) {

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 11
2 Runtime error 1 ms 596 KB Execution killed with signal 11
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Correct 8 ms 348 KB Output is correct
5 Correct 12 ms 348 KB Output is correct
6 Runtime error 2 ms 604 KB Execution killed with signal 11
7 Correct 50 ms 604 KB Output is correct
8 Correct 58 ms 604 KB Output is correct
9 Correct 71 ms 1116 KB Output is correct
10 Correct 155 ms 1116 KB Output is correct
11 Correct 205 ms 1628 KB Output is correct
12 Correct 261 ms 2140 KB Output is correct
13 Correct 318 ms 2452 KB Output is correct
14 Correct 398 ms 2940 KB Output is correct
15 Correct 432 ms 6196 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2672 ms 7212 KB Output is correct
2 Correct 3053 ms 6900 KB Output is correct
3 Correct 4372 ms 9584 KB Output is correct
4 Runtime error 29 ms 6224 KB Execution killed with signal 11
5 Runtime error 36 ms 9324 KB Execution killed with signal 11
6 Runtime error 33 ms 10288 KB Execution killed with signal 11
7 Runtime error 65 ms 13652 KB Execution killed with signal 11
8 Runtime error 48 ms 24404 KB Execution killed with signal 11
9 Runtime error 86 ms 29216 KB Execution killed with signal 11
10 Runtime error 113 ms 40532 KB Execution killed with signal 11
11 Runtime error 106 ms 37460 KB Execution killed with signal 11
12 Runtime error 121 ms 33048 KB Execution killed with signal 11
13 Runtime error 127 ms 34576 KB Execution killed with signal 11
14 Runtime error 99 ms 36136 KB Execution killed with signal 11
15 Runtime error 126 ms 43168 KB Execution killed with signal 11
16 Runtime error 121 ms 54088 KB Execution killed with signal 11
17 Runtime error 131 ms 51016 KB Execution killed with signal 11