oj.uz

Submission #1019490

# Submission time Handle Problem Language Result Execution time Memory
1019490 2024-07-11T00:04:34 Z vjudge1 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 50204 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 200100
#define SZ 410
int CC,in[N],out[N],id[N],prc[SZ][SZ],hv[SZ],CC2,reg[N],ANS,T[N];
vector<int>hav[N],adj[N];
unordered_map<int,int> sup[SZ],sub[SZ];
void upd(unordered_map<int,int>&mp,int x,int v){
    while(x<N)mp[x]+=v,x+=x&-x;
}
void query(unordered_map<int,int>&mp,int x,int v){
    while(x) if(mp.count(x))
        ANS+=mp[x]*v,x-=x&-x;
}
void upd2(int x,int v){
    while(x<N) T[x]+=v,x+=x&-x;
}
void query2(int x,int v){
    while(x) ANS+=T[x]*v,x-=x&-x;
}
void dfs(int n){
    if(id[reg[n]])for(int i=1;i<SZ;i++)
        prc[i][id[reg[n]]]+=hv[i];
    hv[id[reg[n]]]++; in[n]=++CC;
    for(auto i:adj[n])dfs(i);
    hv[id[reg[n]]]--; out[n]=CC;
    if(id[reg[n]])
        upd(sup[id[reg[n]]],in[n],1),
        upd(sup[id[reg[n]]],out[n]+1,-1),
        upd(sub[id[reg[n]]],in[n],1);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q,r;
    cin>>n>>r>>q;
    cin>>reg[1];
    for(int i=2;i<=n;i++){
        int p;cin>>p>>reg[i];
        adj[p].push_back(i);
    }
    for(int i=1;i<=n;i++)
        hav[reg[i]].push_back(i);
    for(int i=1;i<=r;i++)
        if(hav[i].size()>=500)
            id[i]=++CC2;
    dfs(1);
    while(q--){
        int a,b;
        cin>>a>>b;
        ANS=0;
        if(id[a]&&id[b])
            ANS=prc[id[a]][id[b]];
        else if(id[a]||id[b])
            if(hav[a].size()>hav[b].size())
                for(auto i:hav[b])
                    query(sup[id[a]],in[i],1);
            else for(auto i:hav[a])
                query(sub[id[b]],in[i]-1,-1),
                query(sub[id[b]],out[i],1);
        else {
            for(auto i:hav[a])
                upd2(in[i],1),
                upd2(out[i]+1,-1);
            for(auto i:hav[b])
                query2(in[i],1);
            for(auto i:hav[a])
                upd2(in[i],-1),
                upd2(out[i]+1,1);
        }
        cout<<ANS<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Correct 7 ms 9816 KB Output is correct
6 Correct 17 ms 9816 KB Output is correct
7 Correct 22 ms 9884 KB Output is correct
8 Correct 28 ms 10072 KB Output is correct
9 Correct 36 ms 10584 KB Output is correct
10 Correct 64 ms 10388 KB Output is correct
11 Correct 122 ms 10584 KB Output is correct
12 Correct 146 ms 11352 KB Output is correct
13 Correct 182 ms 10840 KB Output is correct
14 Correct 334 ms 11468 KB Output is correct
15 Correct 396 ms 15192 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8061 ms 23396 KB Time limit exceeded
2 Execution timed out 8068 ms 24172 KB Time limit exceeded
3 Execution timed out 8055 ms 26844 KB Time limit exceeded
4 Correct 346 ms 11352 KB Output is correct
5 Correct 350 ms 13912 KB Output is correct
6 Execution timed out 8048 ms 17328 KB Time limit exceeded
7 Correct 2332 ms 13768 KB Output is correct
8 Execution timed out 8032 ms 21848 KB Time limit exceeded
9 Correct 3392 ms 19532 KB Output is correct
10 Correct 6260 ms 26192 KB Output is correct
11 Correct 5672 ms 18508 KB Output is correct
12 Execution timed out 8015 ms 27508 KB Time limit exceeded
13 Execution timed out 8042 ms 28020 KB Time limit exceeded
14 Execution timed out 8021 ms 39316 KB Time limit exceeded
15 Execution timed out 8042 ms 34960 KB Time limit exceeded
16 Execution timed out 8013 ms 41372 KB Time limit exceeded
17 Execution timed out 8085 ms 50204 KB Time limit exceeded