oj.uz

Submission #1109414

# Submission time Handle Problem Language Result Execution time Memory
1109414 2024-11-06T16:10:01 Z sano Regions (IOI09_regions) C++14
0 / 100
 127 ms 61524 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(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<ll, ll>
#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<ll>> g;
vec<ll> eul1, eul2;
vec<vec<ll>> odp;
vec<ll> e;
vec<vec<ll>> m;
ll ti = 0;

void DFS(ll x, ll 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<ll>& a, vec<ll>& b) {
	return a.size() > b.size();
}

void DFS2(ll x, ll pr, ll k, ll 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");
	ll n, r, q;
	cin >> n >> r >> q;
	vec<vec<ll>> 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) {
		ll 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<ll> s_n(r);
	For(i, reg.size()) {
		if (reg[i].size() == 0) s_n[i] = -1;
		s_n[e[reg[i][0]]] = i;
	}
	ll odm = sqrt(n);
	vec<ll> 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) {
		ll r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (s_n[r1] >= odp.size()) {
			ll vys = 0;
			for (auto i : reg[s_n[r1]]) {
				ll q1 = lower_bound(m[r2].begin(), m[r2].end(), eul1[i]) - m[r2].begin();
				ll q2 = upper_bound(m[r2].begin(), m[r2].end(), eul2[i]) - m[r2].begin();
				vys += q2 - q1;
			}
			cout << vys << '\n';
		}
		else {
			cout << odp[s_n[r1]][r2] << '\n';
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:96:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long 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<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   if (s_n[r1] >= odp.size()) {

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 11
2 Runtime error 1 ms 592 KB Execution killed with signal 11
3 Runtime error 1 ms 592 KB Execution killed with signal 11
4 Execution timed out 1 ms 336 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 336 KB Time limit exceeded (wall clock)
6 Runtime error 2 ms 848 KB Execution killed with signal 11
7 Execution timed out 1 ms 592 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 592 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 1104 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 1360 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 1872 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 2640 KB Time limit exceeded (wall clock)
13 Execution timed out 8 ms 3152 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 3664 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 6992 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 59 ms 8836 KB Time limit exceeded (wall clock)
2 Execution timed out 46 ms 8784 KB Time limit exceeded (wall clock)
3 Execution timed out 34 ms 11344 KB Time limit exceeded (wall clock)
4 Runtime error 17 ms 7848 KB Execution killed with signal 11
5 Runtime error 20 ms 11088 KB Execution killed with signal 11
6 Runtime error 28 ms 12704 KB Execution killed with signal 11
7 Runtime error 37 ms 17232 KB Execution killed with signal 11
8 Runtime error 56 ms 28840 KB Execution killed with signal 11
9 Runtime error 77 ms 36680 KB Execution killed with signal 11
10 Runtime error 85 ms 47500 KB Execution killed with signal 11
11 Runtime error 127 ms 47944 KB Execution killed with signal 11
12 Runtime error 103 ms 41220 KB Execution killed with signal 11
13 Runtime error 99 ms 43292 KB Execution killed with signal 11
14 Runtime error 99 ms 45964 KB Execution killed with signal 11
15 Runtime error 104 ms 51280 KB Execution killed with signal 11
16 Runtime error 124 ms 61524 KB Execution killed with signal 11
17 Runtime error 117 ms 59848 KB Execution killed with signal 11