oj.uz

Submission #964912

# Submission time Handle Problem Language Result Execution time Memory
964912 2024-04-17T17:15:59 Z PieArmy Regions (IOI09_regions) C++17
89 / 100
 2169 ms 130976 KB 
typedef long long ll;;
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

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

ll 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]];
    ll tavan=-1;
    int apos=0;
    ll 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<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(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;
    }
}

int 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 'int 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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 5 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 6 ms 8792 KB Output is correct
6 Correct 12 ms 8792 KB Output is correct
7 Correct 15 ms 8792 KB Output is correct
8 Correct 17 ms 9048 KB Output is correct
9 Correct 28 ms 9304 KB Output is correct
10 Correct 69 ms 9556 KB Output is correct
11 Correct 73 ms 9560 KB Output is correct
12 Correct 91 ms 10228 KB Output is correct
13 Correct 108 ms 9704 KB Output is correct
14 Correct 141 ms 14456 KB Output is correct
15 Runtime error 170 ms 18864 KB Execution killed with signal 13

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 21536 KB Output is correct
2 Runtime error 733 ms 17936 KB Execution killed with signal 13
3 Correct 1263 ms 22456 KB Output is correct
4 Correct 182 ms 10472 KB Output is correct
5 Correct 241 ms 12204 KB Output is correct
6 Correct 545 ms 50448 KB Output is correct
7 Correct 761 ms 59676 KB Output is correct
8 Correct 961 ms 71704 KB Output is correct
9 Correct 1342 ms 18048 KB Output is correct
10 Correct 2033 ms 130976 KB Output is correct
11 Correct 2169 ms 17556 KB Output is correct
12 Correct 832 ms 75484 KB Output is correct
13 Runtime error 1110 ms 75576 KB Execution killed with signal 13
14 Correct 1705 ms 87960 KB Output is correct
15 Correct 1808 ms 112660 KB Output is correct
16 Correct 1835 ms 124000 KB Output is correct
17 Correct 1953 ms 106808 KB Output is correct