oj.uz

Submission #933052

# Submission time Handle Problem Language Result Execution time Memory
933052 2024-02-24T23:45:21 Z vjudge1 Regions (IOI09_regions) C++17
25 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
#include <map>
using namespace std;
#define ptr(x) shared_ptr<x>
const int maxn = 2e5 + 54;

int region[maxn];
vector<int>adj[maxn];
int euler[maxn]; int ini[maxn], fin[maxn];
int resp[550][550];
int pos = 0;
int n, r, q; 
void dfs(int yo, int padre)
{
	ini[yo] = pos;
	euler[pos++] = yo;
	for (int v: adj[yo])
		if (v != padre) dfs(v, yo);
	fin[yo] = pos;
}
struct nodo
{
	ptr(nodo) lson, rson;
	int l, r;
	map<int, int> mp;
	nodo()
	{
		lson = nullptr; rson = nullptr;
	}
};
struct mst 
{
	ptr(nodo) raiz;
	mst()
	{
		raiz = (ptr(nodo))(new nodo);	
		build(raiz, 0, n-1);
	}
	void build (ptr(nodo) x, int l, int r)
	{
		x->l = l; x->r = r;
		if (l == r)
		{
			x->mp[region[euler[l]]]++;
			return;
		}
		x->lson = (ptr(nodo))(new nodo); x->rson = (ptr(nodo))(new nodo);	
		int mit = (l+r)>>1;
		build(x->lson, l, mit); build(x->rson, mit+1, r);
		x->mp = x->lson->mp;
		for (auto it: x->rson->mp)
			x->mp[it.first] += it.second;
	}
	map<int, int> query (ptr(nodo) node, const int &l, const int &r)
	{
		int currL = node->l, currR = node->r; map<int, int>mp;
		if (currR < l || r < currL) return mp;
		if (l <= currL && currR <= r) return node->mp;
		int mit = (l+r)>>1;
		mp = query(node->lson, l, r); map<int, int> mp2 = query(node->rson, l, r);

		for (auto it: mp2)
			mp[it.first] += it.second;
		return mp;
	}
};
int main() 
{
	cin >> n >> r >> q;
	cin >> region[0]; int padre;
	for (int i = 1; i < n; i++)
	{
		cin >> padre; padre--; cin >> region[i];
		adj[padre].push_back(i);
		adj[i].push_back(padre);
	}
	dfs(0, -1);
	mst segtree;
	//l;

// << ini[i] << " " << fin[i] << endl;
	for (int i = 0; i < n; i++)
	{
		map<int, int> temp = segtree.query(segtree.raiz, ini[i], fin[i]-1);
		int yo = region[i];
		for (auto it: temp)
		{
			resp[yo][it.first]+=it.second;
		}
	}

	
	int a, b;
	while (q--)
	{
		cin >> a >> b;
		cout << resp[a][b] << endl;
	}
}

Compilation message

regions.cpp: In member function 'std::map<int, int> mst::query(std::shared_ptr<nodo>, const int&, const int&)':
regions.cpp:59:7: warning: unused variable 'mit' [-Wunused-variable]
   59 |   int mit = (l+r)>>1;
      |       ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 7 ms 8792 KB Output is correct
6 Correct 36 ms 9304 KB Output is correct
7 Correct 22 ms 9816 KB Output is correct
8 Correct 41 ms 10072 KB Output is correct
9 Correct 469 ms 12652 KB Output is correct
10 Correct 150 ms 16348 KB Output is correct
11 Correct 363 ms 19740 KB Output is correct
12 Correct 2365 ms 24092 KB Output is correct
13 Correct 182 ms 26444 KB Output is correct
14 Correct 362 ms 29728 KB Output is correct
15 Correct 4907 ms 39068 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 5945 ms 56760 KB Output is correct
2 Correct 1804 ms 59548 KB Output is correct
3 Execution timed out 8038 ms 69536 KB Time limit exceeded
4 Runtime error 1546 ms 68396 KB Execution killed with signal 11
5 Runtime error 93 ms 80888 KB Execution killed with signal 11
6 Runtime error 120 ms 102004 KB Execution killed with signal 11
7 Runtime error 2453 ms 131072 KB Execution killed with signal 9
8 Runtime error 2372 ms 131072 KB Execution killed with signal 9
9 Runtime error 221 ms 131072 KB Execution killed with signal 9
10 Runtime error 226 ms 131072 KB Execution killed with signal 9
11 Runtime error 249 ms 131072 KB Execution killed with signal 9
12 Runtime error 255 ms 131072 KB Execution killed with signal 9
13 Runtime error 237 ms 131072 KB Execution killed with signal 9
14 Runtime error 254 ms 131072 KB Execution killed with signal 9
15 Runtime error 240 ms 131072 KB Execution killed with signal 9
16 Runtime error 234 ms 131072 KB Execution killed with signal 9
17 Runtime error 234 ms 131072 KB Execution killed with signal 9