| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 964831 | codefox | Regions (IOI09_regions) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define pii pair<int, short>
vector<vector<int>> graph;
vector<short> region;
vector<int> rind;
vector<int> start;
vector<int> ende;
int c =0 ;
vector<vector<int>> dpback;
vector<vector<ll>> backsolutions;
vector<vector<ll>> frontsolutions;
int K = 200;
void dfsback(int i)
{
start[i] = c++;
for (int ele:graph[i])
{
dfsback(ele);
for (int j = 0; j < K; j++)
{
dpback[i][j] += dpback[ele][j];
}
}
for (int j = 0; j < K; j++)
{
backsolutions[region[i]][j] = dpback[i][j];
}
if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
ende[i] = c;
}
void dfsfront(int i, vector<int> dpfront)
{
for (int j = 0; j < K; j++)
{
frontsolutions[j][region[i]] = dpfront[j];
}
if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
for (int ele:graph[i])
{
dfsfront(ele, dpfront);
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, r, q;
cin >> n >> r >> q;
graph.assign(n, vector<int>());
region.assign(n, 0);
rind.assign(r, -1);
start.assign(n, 0);
ende.assign(n, 0);
dpback.assign(n, vector<int>(K, 0));
backsolutions.assign(r, vector<int>(K, -1));
vector<vector<int>> part(r);
cin >> region[0];
region[0]--;
part[region[0]].push_back(0);
for (int i = 1; i < n; i++)
{
int b;
cin >> b;
graph[b-1].push_back(i);
cin >> region[i];
region[i]--;
part[region[i]].push_back(i);
}
vector<int> rsum(r);
int d =0;
for (int i = 0; i < n; i++) rsum[region[i]]++;
for (int i = 0; i < r; i++)
{
if (rsum[i]> (n+K)/K)
{
rind[i] = d++;
}
}
rsum.resize(0);
dfsback(0);
dpback.resize(0);
frontsolutions.assign(K, vector<int>(r, -1));
dfsfront(0, vector<int>(K, 0));
while (q--)
{
int a, b;
cin >> a >> b;
a--; b--;
if (rsum[a]>K) cout << frontsolutions[rind[a]][b] << endl;
else if (rsum[b]>K) cout << backsolutions[a][rind[b]] << endl;
else
{
vector<pii> s;
for (int ele:part[a])
{
s.push_back({start[ele], 0});
s.push_back({ende[ele], 1});
}
for (int ele:part[b])
{
s.push_back({start[ele], 2});
}
sort(s.begin(), s.end());
int open = 0;
int sol = 0;
for (pii ele:s)
{
if (ele.second == 0) open++;
if (ele.second == 1) open--;
if (ele.second == 2) sol += open;
}
cout << sol << endl;
}
}
return 0;
}