oj.uz

Submission #964909

# Submission time Handle Problem Language Result Execution time Memory
964909 2024-04-17T17:14:27 Z PieArmy Regions (IOI09_regions) C++17
84 / 100
 2153 ms 131072 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 3 ms 11092 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 4 ms 8812 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 15 ms 8792 KB Output is correct
7 Correct 14 ms 8792 KB Output is correct
8 Correct 24 ms 8792 KB Output is correct
9 Correct 38 ms 9304 KB Output is correct
10 Correct 53 ms 9304 KB Output is correct
11 Correct 71 ms 9560 KB Output is correct
12 Correct 99 ms 10144 KB Output is correct
13 Correct 104 ms 9832 KB Output is correct
14 Runtime error 140 ms 14516 KB Execution killed with signal 13
15 Correct 172 ms 18780 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 21540 KB Output is correct
2 Correct 756 ms 17868 KB Output is correct
3 Correct 1217 ms 22188 KB Output is correct
4 Runtime error 193 ms 10496 KB Execution killed with signal 13
5 Correct 236 ms 12412 KB Output is correct
6 Correct 530 ms 50416 KB Output is correct
7 Correct 796 ms 56892 KB Output is correct
8 Correct 954 ms 72172 KB Output is correct
9 Runtime error 1286 ms 18096 KB Execution killed with signal 13
10 Correct 2064 ms 131072 KB Output is correct
11 Correct 2153 ms 17280 KB Output is correct
12 Correct 871 ms 75660 KB Output is correct
13 Runtime error 1117 ms 75576 KB Execution killed with signal 13
14 Correct 1713 ms 88196 KB Output is correct
15 Correct 1786 ms 112648 KB Output is correct
16 Correct 1873 ms 123992 KB Output is correct
17 Correct 1894 ms 105496 KB Output is correct