oj.uz

답안 #1019493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019493 2024-07-11T00:23:06 Z boyliguanhan Regions (IOI09_regions) C++17
100 / 100
 7458 ms 68100 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(3)
using namespace __gnu_pbds;
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];
gp_hash_table<int,int> sup[SZ],sub[SZ],sup2[SZ],sub2[SZ];
void upd(gp_hash_table<int,int>&mp,int x,int v){
    while(x<N)mp[x]+=v,x+=x&-x;
}
void query(gp_hash_table<int,int>&mp,int x,int v){
    while(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<=CC2;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);
    for(int i=1;i<=CC2;i++)
        sub2[i]=sub[i],sup2[i]=sup[i];
    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;
        if(q%500==0)for(int i=1;i<=CC2;i++)
            sub[i]=sub2[i],sup[i]=sup2[i];
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 10072 KB Output is correct
3 Correct 6 ms 10072 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 7 ms 10072 KB Output is correct
6 Correct 13 ms 10328 KB Output is correct
7 Correct 28 ms 10328 KB Output is correct
8 Correct 28 ms 10328 KB Output is correct
9 Correct 34 ms 10840 KB Output is correct
10 Correct 66 ms 10584 KB Output is correct
11 Correct 122 ms 10840 KB Output is correct
12 Correct 131 ms 11608 KB Output is correct
13 Correct 193 ms 11096 KB Output is correct
14 Correct 342 ms 11608 KB Output is correct
15 Correct 424 ms 14680 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3105 ms 33620 KB Output is correct
2 Correct 3837 ms 38708 KB Output is correct
3 Correct 4931 ms 34864 KB Output is correct
4 Correct 342 ms 11608 KB Output is correct
5 Correct 364 ms 13656 KB Output is correct
6 Correct 2092 ms 23564 KB Output is correct
7 Correct 2493 ms 13856 KB Output is correct
8 Correct 2478 ms 21324 KB Output is correct
9 Correct 3540 ms 19332 KB Output is correct
10 Correct 6425 ms 25168 KB Output is correct
11 Correct 5865 ms 18756 KB Output is correct
12 Correct 2199 ms 35172 KB Output is correct
13 Correct 3190 ms 35604 KB Output is correct
14 Correct 5637 ms 55264 KB Output is correct
15 Correct 5199 ms 40272 KB Output is correct
16 Correct 5268 ms 47584 KB Output is correct
17 Correct 7458 ms 68100 KB Output is correct