| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1103745 | salmon | 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;
#define pb(x) push_back(x)
int N;
int K,Q;
int parent[200100];
vector<int> children[200100];
int lst[200100];
vector<int> kv[200100];
vector<int> pov[200100];
vector<int> prv[200100];
int pre[200100];
int invpre[200100];
int post[200100];
int cont = 0;
const int B = 1001;
long long int ans[200100/B + 100][25100];
long long int ans1[25100][200100/B + 100];
vector<int> f;
long long int fk[25100][200100/B + 100];
map<int,int> mep;
int h1,h;
void dfs(int i){
pre[i] = cont;
invpre[cont] = i;
cont++;
for(int j : children[i]){
dfs(j);
}
post[i] = cont - 1;
}
void fil(int i){
for(pair<int,int> ii : mep){
ans[ii.first][lst[i]] += ii.second;
}
if(kv[lst[i]].size() >= B){
mep[lst[i]]++;
}
for(int j : children[i]){
fil(j);
}
if(kv[lst[i]].size() >= B){
mep[lst[i]]--;
}
}
int main(){
scanf(" %d",&N);
scanf(" %d",&K);
scanf(" %d",&Q);
parent[1] = -1;
scanf(" %d",&lst[1]);
kv[lst[1]].push_back(1);
for(int i = 2; i <= N; i++){
scanf(" %d",&parent[i]);
scanf(" %d",&lst[i]);
children[parent[i]].pb(i);
kv[lst[i]].push_back(i);
}
dfs(1);
//printf("s %d",pre[1]);
for(int i = 1; i <= K; i++){
if(!kv[i].empty()){
for(int j : kv[i]){
pov[i].push_back(post[j]);
prv[i].push_back(pre[j]);
}
sort(pov[i].begin(),pov[i].end());
sort(prv[i].begin(),prv[i].end());
pov[i].push_back(N + 5);
prv[i].push_back(N + 5);
}
if(kv[i].size() >= B){
f.push_back(i);
}
}
return;
for(int i = 0; i < N; i++){
for(int j = 0; j < f.size(); j++){
fk[i][j] = 0;
}
}
for(int i = 0; i < N; i++){
if(i != 0){
for(int j = 0; j < f.size(); j++){
fk[i][j] = fk[i - 1][j];
}
}
if(kv[invpre[i]].size() >= B){
int h = invpre[i];
int in = lower_bound(f.begin(),f.end(),h) - f.begin();
fk[i][in]++;
}
}
for(int i = 1; i <= K; i++){
for(int j = 0; j < f.size(); j++){
ans1[i][j] = 0;
}
}
for(int j = 0; j < f.size(); j++){
for(int i = 1; i <= K; i++){
ans[j][i] = 0;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < f.size(); j++){
int in = invpre[i];
ans1[lst[in]][j] += fk[post[in]][j] - fk[pre[in]][j];
}
}
fil(1);
/*for(int i = 1; i <= K; i++){
for(int j : prv[i]){
printf("%d ",j);
}
printf("\n");
}
for(int i = 1; i <= K; i++){
for(int j : pov[i]){
printf("%d ",j);
}
printf("\n");
}*/
for(int i = 0; i < Q; i++){
scanf(" %d",&h);
scanf(" %d",&h1);
if(kv[h].size() == 0 || kv[h1].size() == 0){
printf("0\n");
}
else if(kv[h].size() >= B){
int in = lower_bound(f.begin(),f.end(),h) - f.begin();
printf("%d\n",ans[in][h1]);
}
else if(kv[h1].size() >= B){
int in = lower_bound(f.begin(),f.end(),h1) - f.begin();
printf("%d\n",ans1[h][in]);
}
else{
int it = 0;
int it1 = 0;
long long int V = 0;
int v = 0;
for(int i = 0; i < prv[h1].size() + prv[h].size() - 2; i++){
if(prv[h1][it1] <= prv[h][it]){
v++;
it1++;
}
else{
V -= v;
it++;
}
}
it = 0;
it1 = 0;
v = 0;
for(int i = 0; i < prv[h1].size() + pov[h].size() - 2; i++){
if(prv[h1][it1] <= pov[h][it]){
v++;
it1++;
}
else{
V += v;
it++;
}
}
printf("%d\n",V);
}
fflush(stdout);
}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
*/