oj.uz

Submission #892688

# Submission time Handle Problem Language Result Execution time Memory
892688 2023-12-25T16:52:46 Z winter0101 Regions (IOI09_regions) C++14
100 / 100
 1831 ms 72388 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+500+9;
const int block=500;
int x[maxn/block][25009],y[25009][maxn/block],h[maxn];
vector<int>value[25009];
vector<int>a[maxn];
vector<int>euler[25009];
vector<int>only[25009];
int large[maxn],rep[maxn];
int in[maxn],out[maxn],tme=0;
void dfs(int u){
in[u]=++tme;
for (auto v:a[u]){
    dfs(v);
}
out[u]=tme;
}
int sum[maxn];
int nw[maxn];
int cnt;
void redfs(int u){
if (rep[h[u]]){
nw[rep[h[u]]]++;
}
for1(j,1,cnt){
x[j][h[u]]+=nw[j];
}
for (auto v:a[u]){
redfs(v);
}
if (rep[h[u]]){
nw[rep[h[u]]]--;
}
}
int dd[maxn];
void cal(int x1,int y1){
if (rep[y1]){
cout<<y[x1][rep[y1]]<<endl;
return;
}
if (rep[x1]){
cout<<x[rep[x1]][y1]<<endl;
return;
}
int ans=0;
int now=0;
int p=-1;
for(auto v:euler[x1]){
for1(j,p+1,sz(only[y1])-1){
if (only[y1][j]<=v)p=j,now++;
else break;
}
dd[v]=now;
}
for (auto v:value[x1]){
ans+=dd[out[v]]-dd[in[v]-1];
}
for (auto v:euler[x1]){
dd[v]=0;
}
cout<<ans<<endl;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,r,q;
    cin>>n>>r>>q;
    for1(i,1,n){
    cin>>h[i];
    if (i==1){
    value[h[i]].pb(i);
    continue;
    }
    int p;
    cin>>p;
    swap(p,h[i]);
    value[h[i]].pb(i);
    a[p].pb(i);
    }
    dfs(1);
    cnt=0;
    for1(i,1,r){
    if (sz(value[i])>=block){
    cnt++;
    large[cnt]=i;
    rep[i]=cnt;
    }
    }
    for1(i,1,cnt){
    for1(j,1,n)sum[j]=0;
    for(auto v:value[large[i]]){
    sum[in[v]]++;
    }
    for1(j,1,n)sum[j]+=sum[j-1];
    for1(j,1,r){
    if (j==large[i])continue;
    for (auto v:value[j]){
    y[j][i]+=sum[out[v]]-sum[in[v]-1];
    }
    }
    }
    redfs(1);
    for1(i,1,n){
    if (in[i]>1)euler[h[i]].pb(in[i]-1);
    euler[h[i]].pb(out[i]);
    only[h[i]].pb(in[i]);
    }
    for1(i,1,r){
    sort(all(euler[i]));
    euler[i].resize(distance(euler[i].begin(),unique(all(euler[i]))));
    sort(all(only[i]));
    only[i].resize(distance(only[i].begin(),unique(all(only[i]))));
    }
    for1(i,1,q){
    int x1,y1;
    cin>>x1>>y1;
    cal(x1,y1);
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10740 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 9 ms 10584 KB Output is correct
7 Correct 13 ms 10840 KB Output is correct
8 Correct 15 ms 10840 KB Output is correct
9 Correct 22 ms 11096 KB Output is correct
10 Correct 47 ms 11404 KB Output is correct
11 Correct 61 ms 11740 KB Output is correct
12 Correct 78 ms 12320 KB Output is correct
13 Correct 88 ms 12100 KB Output is correct
14 Correct 119 ms 12764 KB Output is correct
15 Correct 157 ms 15392 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 18396 KB Output is correct
2 Correct 661 ms 17336 KB Output is correct
3 Correct 1014 ms 20356 KB Output is correct
4 Correct 148 ms 12776 KB Output is correct
5 Correct 209 ms 14408 KB Output is correct
6 Correct 481 ms 29084 KB Output is correct
7 Correct 712 ms 15280 KB Output is correct
8 Correct 638 ms 38308 KB Output is correct
9 Correct 1152 ms 23984 KB Output is correct
10 Correct 1571 ms 28760 KB Output is correct
11 Correct 1831 ms 23960 KB Output is correct
12 Correct 748 ms 50188 KB Output is correct
13 Correct 951 ms 50376 KB Output is correct
14 Correct 1071 ms 58668 KB Output is correct
15 Correct 1505 ms 67540 KB Output is correct
16 Correct 1527 ms 72388 KB Output is correct
17 Correct 1585 ms 67340 KB Output is correct