oj.uz

Submission #1109419

# Submission time Handle Problem Language Result Execution time Memory
1109419 2024-11-06T16:15:13 Z sano Regions (IOI09_regions) C++14
26 / 100
 4408 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);
	For(i, reg.size()) {
		if (reg[i].size() == 0) s_n[i] = -1;
		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] >= 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:106: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]
  106 |   if (s_n[r1] >= odp.size()) {

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Runtime error 1 ms 592 KB Execution killed with signal 11
3 Runtime error 2 ms 592 KB Execution killed with signal 11
4 Correct 7 ms 336 KB Output is correct
5 Correct 12 ms 336 KB Output is correct
6 Runtime error 2 ms 592 KB Execution killed with signal 11
7 Correct 52 ms 592 KB Output is correct
8 Correct 68 ms 592 KB Output is correct
9 Correct 86 ms 1104 KB Output is correct
10 Correct 152 ms 1104 KB Output is correct
11 Correct 211 ms 1616 KB Output is correct
12 Correct 287 ms 2128 KB Output is correct
13 Correct 316 ms 2632 KB Output is correct
14 Correct 414 ms 2932 KB Output is correct
15 Correct 423 ms 6200 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2724 ms 7224 KB Output is correct
2 Correct 3040 ms 6900 KB Output is correct
3 Correct 4408 ms 9580 KB Output is correct
4 Runtime error 15 ms 6224 KB Execution killed with signal 11
5 Runtime error 20 ms 9552 KB Execution killed with signal 11
6 Runtime error 23 ms 10320 KB Execution killed with signal 11
7 Runtime error 33 ms 13752 KB Execution killed with signal 11
8 Runtime error 46 ms 24396 KB Execution killed with signal 11
9 Runtime error 93 ms 29224 KB Execution killed with signal 11
10 Runtime error 80 ms 40352 KB Execution killed with signal 11
11 Runtime error 90 ms 37404 KB Execution killed with signal 11
12 Runtime error 90 ms 33136 KB Execution killed with signal 11
13 Runtime error 80 ms 34672 KB Execution killed with signal 11
14 Runtime error 104 ms 36044 KB Execution killed with signal 11
15 Runtime error 94 ms 43096 KB Execution killed with signal 11
16 Runtime error 99 ms 54088 KB Execution killed with signal 11
17 Runtime error 97 ms 51092 KB Execution killed with signal 11