oj.uz

Submission #1109427

# Submission time Handle Problem Language Result Execution time Memory
1109427 2024-11-06T16:26:31 Z sano Regions (IOI09_regions) C++14
41 / 100
 5143 ms 33608 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;
		}
		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:110: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]
  110 |   if (s_n[r1] >= odp.size()) {

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 12 ms 336 KB Output is correct
6 Incorrect 4 ms 336 KB Output isn't correct
7 Correct 43 ms 592 KB Output is correct
8 Correct 58 ms 592 KB Output is correct
9 Correct 95 ms 1280 KB Output is correct
10 Correct 135 ms 1268 KB Output is correct
11 Correct 205 ms 1616 KB Output is correct
12 Correct 253 ms 2128 KB Output is correct
13 Correct 326 ms 2440 KB Output is correct
14 Correct 402 ms 2944 KB Output is correct
15 Correct 436 ms 6200 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2567 ms 7220 KB Output is correct
2 Correct 3076 ms 6900 KB Output is correct
3 Correct 4318 ms 9588 KB Output is correct
4 Incorrect 67 ms 3284 KB Output isn't correct
5 Runtime error 77 ms 4900 KB Execution killed with signal 13
6 Incorrect 146 ms 7044 KB Output isn't correct
7 Incorrect 1522 ms 9076 KB Output isn't correct
8 Correct 2033 ms 17224 KB Output is correct
9 Runtime error 1302 ms 14672 KB Execution killed with signal 13
10 Runtime error 1832 ms 31424 KB Execution killed with signal 13
11 Runtime error 2574 ms 18808 KB Execution killed with signal 13
12 Runtime error 112 ms 33608 KB Execution killed with signal 11
13 Runtime error 990 ms 17748 KB Execution killed with signal 13
14 Runtime error 1185 ms 19968 KB Execution killed with signal 13
15 Correct 5143 ms 22836 KB Output is correct
16 Correct 5125 ms 30104 KB Output is correct
17 Runtime error 1490 ms 29868 KB Execution killed with signal 13