oj.uz

Submission #892687

# Submission time Handle Problem Language Result Execution time Memory
892687 2023-12-25T16:52:02 Z winter0101 Regions (IOI09_regions) C++14
30 / 100
 2412 ms 131072 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+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[2509];
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 2 ms 10592 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 8 ms 10840 KB Output is correct
7 Correct 14 ms 10840 KB Output is correct
8 Correct 18 ms 10840 KB Output is correct
9 Correct 24 ms 11096 KB Output is correct
10 Correct 47 ms 11408 KB Output is correct
11 Correct 58 ms 11744 KB Output is correct
12 Correct 76 ms 12320 KB Output is correct
13 Correct 87 ms 12096 KB Output is correct
14 Correct 116 ms 12764 KB Output is correct
15 Correct 150 ms 15384 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 20152 KB Output is correct
2 Correct 585 ms 19108 KB Output is correct
3 Correct 991 ms 22116 KB Output is correct
4 Runtime error 18 ms 23884 KB Execution killed with signal 11
5 Runtime error 21 ms 27128 KB Execution killed with signal 6
6 Runtime error 58 ms 60092 KB Execution killed with signal 11
7 Runtime error 30 ms 27724 KB Execution killed with signal 6
8 Runtime error 73 ms 76932 KB Execution killed with signal 6
9 Runtime error 58 ms 36976 KB Execution killed with signal 6
10 Runtime error 58 ms 46268 KB Execution killed with signal 11
11 Runtime error 64 ms 35456 KB Execution killed with signal 6
12 Runtime error 126 ms 97416 KB Execution killed with signal 11
13 Runtime error 118 ms 98124 KB Execution killed with signal 6
14 Runtime error 178 ms 113476 KB Execution killed with signal 11
15 Runtime error 131 ms 130384 KB Execution killed with signal 6
16 Runtime error 2412 ms 131072 KB Execution killed with signal 9
17 Runtime error 163 ms 130972 KB Execution killed with signal 6