oj.uz

Submission #892686

# Submission time Handle Problem Language Result Execution time Memory
892686 2023-12-25T16:51:15 Z winter0101 Regions (IOI09_regions) C++14
30 / 100
 2554 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=300;
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 10836 KB Output is correct
2 Correct 2 ms 10580 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 3 ms 10676 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 10 ms 10584 KB Output is correct
7 Correct 11 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 37 ms 11416 KB Output is correct
11 Correct 56 ms 11740 KB Output is correct
12 Correct 68 ms 12324 KB Output is correct
13 Correct 85 ms 12352 KB Output is correct
14 Correct 113 ms 12764 KB Output is correct
15 Correct 142 ms 15400 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 20360 KB Output is correct
2 Correct 622 ms 19460 KB Output is correct
3 Correct 990 ms 22476 KB Output is correct
4 Runtime error 19 ms 23916 KB Execution killed with signal 11
5 Runtime error 23 ms 27264 KB Execution killed with signal 6
6 Runtime error 94 ms 81160 KB Execution killed with signal 11
7 Runtime error 102 ms 96744 KB Execution killed with signal 6
8 Runtime error 173 ms 114668 KB Execution killed with signal 6
9 Runtime error 187 ms 128476 KB Execution killed with signal 6
10 Runtime error 395 ms 131072 KB Execution killed with signal 9
11 Runtime error 2554 ms 131072 KB Execution killed with signal 9
12 Runtime error 143 ms 122020 KB Execution killed with signal 11
13 Runtime error 129 ms 122676 KB Execution killed with signal 6
14 Runtime error 2317 ms 131072 KB Execution killed with signal 9
15 Runtime error 2351 ms 131072 KB Execution killed with signal 9
16 Runtime error 2407 ms 131072 KB Execution killed with signal 9
17 Runtime error 2409 ms 131072 KB Execution killed with signal 9