oj.uz

Submission #964895

# Submission time Handle Problem Language Result Execution time Memory
964895 2024-04-17T17:05:46 Z PieArmy Regions (IOI09_regions) C++17
85 / 100
 2150 ms 131072 KB 
typedef long long ll;
#include <bits/stdc++.h>
#define pb push_back
#define int ll
using namespace std;

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

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

void code(){
    cin>>n>>R>>Q;
    sq=sqrt(n);
    cin>>renk[1];
    int time=0;
    say[renk[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(say[renk[i]]==sq){
            fazlapos[renk[i]]=time;
            time++;
        }
        say[renk[i]]++;
    }
    function<int(int,int)>f=[&](int pos,int tur)->int{
        int 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,int)>f2=[&](int pos,int tur,int 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(say[renk[pos]]<=sq){
            bas[pos]=time;
            var[renk[pos]].pb(pos);
            sirali[renk[pos]].pb(pos);
        }
        time++;
        for(int x:child[pos]){
            turla(x);
        }
        son[pos]=time-1;
    };
    turla(1);
    for(int i=1;i<=R;i++){
        if(say[i]>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;
    }
}

int32_t main(){
    bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    int t=1;
    if(!t)cin>>t;
    while(t--){code();cout<<endl;}
    return 0;
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:110:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:110:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 5 ms 12888 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 12 ms 12888 KB Output is correct
7 Correct 18 ms 12888 KB Output is correct
8 Correct 22 ms 12888 KB Output is correct
9 Correct 35 ms 13400 KB Output is correct
10 Correct 50 ms 13400 KB Output is correct
11 Correct 76 ms 13700 KB Output is correct
12 Correct 100 ms 14296 KB Output is correct
13 Correct 111 ms 14072 KB Output is correct
14 Correct 140 ms 16696 KB Output is correct
15 Correct 178 ms 21584 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 697 ms 23756 KB Execution killed with signal 13
2 Correct 767 ms 19948 KB Output is correct
3 Correct 1307 ms 24728 KB Output is correct
4 Correct 171 ms 14688 KB Output is correct
5 Correct 250 ms 16848 KB Output is correct
6 Correct 511 ms 52288 KB Output is correct
7 Correct 754 ms 61684 KB Output is correct
8 Correct 1098 ms 80164 KB Output is correct
9 Correct 1324 ms 23096 KB Output is correct
10 Runtime error 658 ms 131072 KB Execution killed with signal 9
11 Correct 2150 ms 22168 KB Output is correct
12 Correct 900 ms 80412 KB Output is correct
13 Correct 1181 ms 81376 KB Output is correct
14 Correct 1768 ms 98500 KB Output is correct
15 Correct 1870 ms 119240 KB Output is correct
16 Runtime error 147 ms 131072 KB Execution killed with signal 9
17 Correct 2025 ms 116648 KB Output is correct