oj.uz

답안 #1019489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1019489 2024-07-11T00:03:04 Z vjudge1 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 48408 KB 
#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
using namespace __gnu_pbds;
#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];
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)  if(mp.find(x)!=mp.end())
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 4 ms 9900 KB Output is correct
3 Correct 5 ms 9896 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 10 ms 10072 KB Output is correct
6 Correct 13 ms 10072 KB Output is correct
7 Correct 26 ms 10072 KB Output is correct
8 Correct 24 ms 10072 KB Output is correct
9 Correct 33 ms 10584 KB Output is correct
10 Correct 70 ms 10584 KB Output is correct
11 Correct 110 ms 10840 KB Output is correct
12 Correct 140 ms 11352 KB Output is correct
13 Correct 179 ms 10840 KB Output is correct
14 Correct 328 ms 11608 KB Output is correct
15 Correct 393 ms 14708 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8061 ms 21724 KB Time limit exceeded
2 Execution timed out 8055 ms 22940 KB Time limit exceeded
3 Execution timed out 8048 ms 24476 KB Time limit exceeded
4 Correct 342 ms 11516 KB Output is correct
5 Correct 353 ms 13656 KB Output is correct
6 Execution timed out 8032 ms 16728 KB Time limit exceeded
7 Correct 2398 ms 13636 KB Output is correct
8 Execution timed out 8067 ms 21080 KB Time limit exceeded
9 Correct 3312 ms 19180 KB Output is correct
10 Correct 6030 ms 24916 KB Output is correct
11 Correct 5470 ms 18588 KB Output is correct
12 Execution timed out 8039 ms 27084 KB Time limit exceeded
13 Execution timed out 8063 ms 27896 KB Time limit exceeded
14 Execution timed out 8029 ms 35048 KB Time limit exceeded
15 Execution timed out 8037 ms 32220 KB Time limit exceeded
16 Execution timed out 8025 ms 39464 KB Time limit exceeded
17 Execution timed out 8034 ms 48408 KB Time limit exceeded