oj.uz

답안 #933053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933053 2024-02-24T23:53:40 Z vjudge1 Regions (IOI09_regions) C++17
13 / 100
 306 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;
	vector<int> mp;
	nodo()
	{
		mp.resize(501);
		lson = nullptr; rson = nullptr;
	}
};
void une (vector<int>&a, vector<int>&b)
{
	for (int i = 0; i <= 500; i++)
		a[i]+=b[i];
}
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;
		une(x->mp, x->rson->mp);
	}
	vector<int> query (ptr(nodo) node, const int &l, const int &r)
	{
		int currL = node->l, currR = node->r; vector<int>mp(501);
		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); vector<int> mp2 = query(node->rson, l, r);

		une(mp, mp2);
		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++)
	{
		vector<int> temp = segtree.query(segtree.raiz, ini[i], fin[i]-1);
		int yo = region[i];
		for (int i = 0; i <= 500; i++)
		{
			resp[yo][i]+=temp[i];
		}
	}

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

Compilation message

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

Subtask #1
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 6 ms 9304 KB Output is correct
5 Correct 10 ms 10860 KB Output is correct
6 Correct 15 ms 12120 KB Output is correct
7 Correct 28 ms 14936 KB Output is correct
8 Correct 31 ms 16984 KB Output is correct
9 Correct 66 ms 30040 KB Output is correct
10 Correct 133 ms 50768 KB Output is correct
11 Correct 234 ms 71780 KB Output is correct
12 Correct 306 ms 92940 KB Output is correct
13 Correct 303 ms 109400 KB Output is correct
14 Runtime error 73 ms 131072 KB Execution killed with signal 9
15 Runtime error 82 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 97 ms 131072 KB Execution killed with signal 9
2 Runtime error 96 ms 131072 KB Execution killed with signal 9
3 Runtime error 105 ms 131072 KB Execution killed with signal 9
4 Runtime error 22 ms 19396 KB Execution killed with signal 11
5 Runtime error 32 ms 21884 KB Execution killed with signal 11
6 Runtime error 34 ms 21352 KB Execution killed with signal 11
7 Runtime error 44 ms 22508 KB Execution killed with signal 11
8 Runtime error 59 ms 30468 KB Execution killed with signal 11
9 Runtime error 90 ms 29328 KB Execution killed with signal 11
10 Runtime error 100 ms 37608 KB Execution killed with signal 11
11 Runtime error 115 ms 32032 KB Execution killed with signal 11
12 Runtime error 118 ms 31284 KB Execution killed with signal 11
13 Runtime error 131 ms 32380 KB Execution killed with signal 11
14 Runtime error 117 ms 32036 KB Execution killed with signal 11
15 Runtime error 119 ms 37640 KB Execution killed with signal 11
16 Runtime error 125 ms 49756 KB Execution killed with signal 11
17 Runtime error 122 ms 46848 KB Execution killed with signal 11