oj.uz

Submission #964902

# Submission time Handle Problem Language Result Execution time Memory
964902 2024-04-17T17:08:51 Z PieArmy Regions (IOI09_regions) C++17
44 / 100
 2217 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],fazlapos[25001];
vector<int>renk,bas,son;
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;
    renk.resize(n+1);
    bas.resize(n+1);
    son.resize(n+1);
    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:114:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:114:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     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 8792 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 5 ms 6744 KB Output is correct
5 Correct 5 ms 6744 KB Output is correct
6 Correct 9 ms 6744 KB Output is correct
7 Correct 24 ms 6744 KB Output is correct
8 Correct 23 ms 6744 KB Output is correct
9 Correct 25 ms 7512 KB Output is correct
10 Correct 51 ms 7512 KB Output is correct
11 Correct 73 ms 7764 KB Output is correct
12 Correct 87 ms 8724 KB Output is correct
13 Correct 101 ms 8480 KB Output is correct
14 Correct 138 ms 15356 KB Output is correct
15 Runtime error 162 ms 18544 KB Execution killed with signal 13

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 23488 KB Output is correct
2 Correct 774 ms 19816 KB Output is correct
3 Runtime error 1261 ms 22804 KB Execution killed with signal 13
4 Runtime error 168 ms 9240 KB Execution killed with signal 13
5 Correct 227 ms 11652 KB Output is correct
6 Runtime error 490 ms 49672 KB Execution killed with signal 13
7 Correct 769 ms 61540 KB Output is correct
8 Correct 1028 ms 80732 KB Output is correct
9 Runtime error 1348 ms 20484 KB Execution killed with signal 13
10 Runtime error 300 ms 131072 KB Execution killed with signal 9
11 Runtime error 2217 ms 20916 KB Execution killed with signal 13
12 Runtime error 890 ms 82740 KB Execution killed with signal 13
13 Runtime error 1193 ms 75628 KB Execution killed with signal 13
14 Runtime error 1932 ms 98920 KB Execution killed with signal 13
15 Runtime error 1893 ms 117796 KB Execution killed with signal 13
16 Runtime error 2004 ms 130500 KB Execution killed with signal 13
17 Correct 1942 ms 119544 KB Output is correct