| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 933053 |
2024-02-24T23:53:40 Z |
vjudge1 |
Regions (IOI09_regions) |
C++17 |
|
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
