oj.uz

Submission #1109424

# Submission time Handle Problem Language Result Execution time Memory
1109424 2024-11-06T16:22:09 Z sano Regions (IOI09_regions) C++14
26 / 100
 4312 ms 53868 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 1 ms 592 KB Execution killed with signal 11
2 Runtime error 3 ms 600 KB Execution killed with signal 11
3 Runtime error 3 ms 592 KB Execution killed with signal 11
4 Correct 8 ms 336 KB Output is correct
5 Correct 13 ms 336 KB Output is correct
6 Runtime error 2 ms 848 KB Execution killed with signal 11
7 Correct 48 ms 592 KB Output is correct
8 Correct 53 ms 604 KB Output is correct
9 Correct 95 ms 1116 KB Output is correct
10 Correct 169 ms 1116 KB Output is correct
11 Correct 224 ms 1628 KB Output is correct
12 Correct 276 ms 2140 KB Output is correct
13 Correct 339 ms 2456 KB Output is correct
14 Correct 418 ms 2936 KB Output is correct
15 Correct 478 ms 6204 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2604 ms 7220 KB Output is correct
2 Correct 3139 ms 6904 KB Output is correct
3 Correct 4312 ms 9584 KB Output is correct
4 Runtime error 15 ms 6224 KB Execution killed with signal 11
5 Runtime error 18 ms 9552 KB Execution killed with signal 11
6 Runtime error 32 ms 10312 KB Execution killed with signal 11
7 Runtime error 44 ms 13828 KB Execution killed with signal 11
8 Runtime error 60 ms 24392 KB Execution killed with signal 11
9 Runtime error 86 ms 29284 KB Execution killed with signal 11
10 Runtime error 103 ms 40524 KB Execution killed with signal 11
11 Runtime error 84 ms 37448 KB Execution killed with signal 11
12 Runtime error 73 ms 33096 KB Execution killed with signal 11
13 Runtime error 96 ms 34624 KB Execution killed with signal 11
14 Runtime error 80 ms 36200 KB Execution killed with signal 11
15 Runtime error 88 ms 43012 KB Execution killed with signal 11
16 Runtime error 97 ms 53868 KB Execution killed with signal 11
17 Runtime error 107 ms 51016 KB Execution killed with signal 11