# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
431640 | juggernaut | Regions (IOI09_regions) | C++17 | 4565 ms | 49956 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>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
#define printl(args...)printf(args)
#else
#define printl(args...)((void)0)
#endif
int n,r,q;
int reg[200005];
vector<int>g[200005];
int timer;
int tin[200005];
int tout[200005];
int precalc[5005][5005];
bool big[25005];
int id[25005];
int tot;
int cnt[25005];
int tmp[25005];
void dfs(int v){
if(big[reg[v]])for(int i=1;i<=tot;i++)precalc[i][id[reg[v]]]+=tmp[i];
tmp[id[reg[v]]]++;
tin[v]=++timer;
for(int to:g[v])dfs(to);
tout[v]=++timer;
tmp[id[reg[v]]]--;
}
vector<pair<int,int>>color[25005];
vector<int>spec[25005];
bool cvota[25005];
unordered_map<int,int>cash[25005];
int main(){
scanf("%d%d%d",&n,&r,&q);
scanf("%d",®[1]);
cnt[reg[1]]++;
for(int i=2;i<=n;i++){
int par;
cnt[reg[i]]++;
scanf("%d%d",&par,®[i]);
g[par].push_back(i);
}
vector<pair<int,int>>vec;
for(int i=1;i<=r;i++)vec.emplace_back(cnt[i],i);
sort(vec.rbegin(),vec.rend());
for(int i=0;i<min((int)vec.size(),1000);i++)cvota[vec[i].sc]=true;
for(int i=1;i<=r;i++)if(cvota[i]){
big[i]=true;
id[i]=++tot;
}
dfs(1);
for(int i=1;i<=n;i++){
spec[reg[i]].push_back(tout[i]);
color[reg[i]].emplace_back(tin[i],tout[i]);
}
for(int i=1;i<=r;i++){
sort(color[i].begin(),color[i].end());
sort(spec[i].begin(),spec[i].end());
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
int ans=0;
if(cash[x].count(y))ans=cash[x][y];
else if(big[x]&&big[y]){
ans=precalc[id[x]][id[y]];
}else if(color[x].size()<color[y].size()){
for(auto to:color[x]){
ans+=(lower_bound(color[y].begin(),color[y].end(),make_pair(to.sc,0))-color[y].begin())-(lower_bound(color[y].begin(),color[y].end(),make_pair(to.fr,0))-color[y].begin());
}
}else{
for(auto to:color[y]){
ans+=(lower_bound(color[x].begin(),color[x].end(),make_pair(to.fr,0))-color[x].begin());
ans-=lower_bound(spec[x].begin(),spec[x].end(),to.fr)-spec[x].begin();
}
}
cash[x][y]=ans;
printf("%d\n",ans);
fflush(stdout);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |