답안 #964917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964917 2024-04-17T17:32:57 Z PieArmy Regions (IOI09_regions) C++17
95 / 100
2076 ms 131072 KB
typedef long long ll;
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int n,sq,R,Q;
int renk[200001],fazlapos[25001],bas[200001],son[200001];
ll pre[25001][447],pre2[447][25001];
vector<int>child[200001],var[25001],sirali[25001];

ll cal(int a,int b){
    if(sirali[b].size()==0||sirali[a].size()==0){
        return 0;
    }
    if(sirali[b].size()>sq){
        return pre[a][fazlapos[b]];
    }
    if(sirali[a].size()>sq){
        return pre2[fazlapos[a]][b];
    }
    int sta[sirali[a].size()];
    ll tavan=-1;
    int apos=0;
    ll ans=0;
    for(int i=0;i<sirali[b].size();i++){
        while(tavan!=-1&&son[sta[tavan]]<bas[var[b][i]]){
            tavan--;
        }
        while(apos<sirali[a].size()&&bas[sirali[a][apos]]<=bas[var[b][i]]){
            if(son[sirali[a][apos]]>=bas[var[b][i]]){
                tavan++;
                sta[tavan]=sirali[a][apos];
            }
            apos++;
        }
        ans+=tavan+1;
    }
    return ans;
}

int main(){
    cin>>n>>R>>Q;
    sq=sqrt(n);
    cin>>renk[1];
    int time=0;
    sirali[renk[1]].pb(1);
    for(int &x:fazlapos)
        x=-1;
    for(int i=2;i<=n;i++){
        int par;cin>>par;
        child[par].pb(i);
        cin>>renk[i];
        if(sirali[renk[i]].size()==sq){
            fazlapos[renk[i]]=time;
            time++;
        }
        sirali[renk[i]].pb(i);
    }
    function<ll(int,int)>f=[&](int pos,int tur)->ll{
        ll res=0;
        for(int x:child[pos]){
            res+=f(x,tur);
        }
        if(renk[pos]==tur)return res+1;
        pre[renk[pos]][fazlapos[tur]]+=res;
        return res;
    };
    function<void(int,int,ll)>f2=[&](int pos,int tur,ll sum)->void{
        if(renk[pos]!=tur)pre2[fazlapos[tur]][renk[pos]]+=sum;
        else sum++;
        for(int x:child[pos]){
            f2(x,tur,sum);
        }
    };
    for(int i=1;i<=R;i++){
        if(fazlapos[i]==-1)continue;
        f(1,i);
        f2(1,i,0);
    }
    time=1;
    function<void(int)>turla=[&](int pos)->void{
        if(sirali[renk[pos]].size()<=sq){
            bas[pos]=time;
            var[renk[pos]].pb(pos);
        }
        time++;
        for(int x:child[pos]){
            turla(x);
        }
        child[pos].clear();
        son[pos]=time-1;
    };
    turla(1);
    for(int i=1;i<=R;i++){
        if(sirali[i].size()>sq)continue;
        sort(sirali[i].begin(),sirali[i].end(),[&](const int &x,const int &y){
            if(bas[x]==bas[y]){
                return son[x]<son[y];
            }
            return bas[x]<bas[y];
        });
    }
    while(Q--){
        int a,b;cin>>a>>b;
        cout<<cal(a,b)<<endl;
    }
}

Compilation message

regions.cpp: In function 'll cal(int, int)':
regions.cpp:15:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if(sirali[b].size()>sq){
      |        ~~~~~~~~~~~~~~~~^~~
regions.cpp:18:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     if(sirali[a].size()>sq){
      |        ~~~~~~~~~~~~~~~~^~~
regions.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<sirali[b].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~
regions.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(apos<sirali[a].size()&&bas[sirali[a][apos]]<=bas[var[b][i]]){
      |               ~~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:53:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if(sirali[renk[i]].size()==sq){
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:82:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if(sirali[renk[pos]].size()<=sq){
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'int main()':
regions.cpp:95:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if(sirali[i].size()>sq)continue;
      |            ~~~~~~~~~~~~~~~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 16 ms 8884 KB Output is correct
8 Correct 25 ms 8792 KB Output is correct
9 Correct 31 ms 9304 KB Output is correct
10 Correct 52 ms 9048 KB Output is correct
11 Correct 68 ms 9304 KB Output is correct
12 Correct 94 ms 9816 KB Output is correct
13 Correct 118 ms 9560 KB Output is correct
14 Correct 155 ms 11960 KB Output is correct
15 Correct 164 ms 16380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 711 ms 18964 KB Output is correct
2 Correct 759 ms 15260 KB Output is correct
3 Correct 1239 ms 19648 KB Output is correct
4 Correct 176 ms 10040 KB Output is correct
5 Correct 242 ms 11932 KB Output is correct
6 Correct 546 ms 50128 KB Output is correct
7 Correct 800 ms 59032 KB Output is correct
8 Correct 1048 ms 77108 KB Output is correct
9 Correct 1287 ms 16820 KB Output is correct
10 Runtime error 934 ms 131072 KB Execution killed with signal 9
11 Correct 2076 ms 16052 KB Output is correct
12 Correct 865 ms 75132 KB Output is correct
13 Correct 1124 ms 75932 KB Output is correct
14 Correct 1819 ms 93588 KB Output is correct
15 Correct 1796 ms 113260 KB Output is correct
16 Correct 1807 ms 124336 KB Output is correct
17 Correct 1968 ms 109392 KB Output is correct