oj.uz

Submission #964883

# Submission time Handle Problem Language Result Execution time Memory
964883 2024-04-17T16:55:21 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 2048 ms 82384 KB 
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

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=say[b]-1;i>=0;i--){
        while(tavan!=-1&&bas[sta[tavan]]>bas[var[b][i]]){
            tavan--;
        }
        while(apos<say[a]&&son[sirali[a][apos]]>=bas[var[b][i]]){
            if(bas[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(son[x]==son[y]){
                return bas[x]>bas[y];
            }
            return son[x]>son[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:116:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:116:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Incorrect 2 ms 8792 KB Output isn't correct
4 Incorrect 5 ms 8792 KB Output isn't correct
5 Incorrect 6 ms 8792 KB Output isn't correct
6 Incorrect 9 ms 8792 KB Output isn't correct
7 Incorrect 16 ms 8792 KB Output isn't correct
8 Incorrect 17 ms 8792 KB Output isn't correct
9 Incorrect 23 ms 9304 KB Output isn't correct
10 Incorrect 48 ms 9300 KB Output isn't correct
11 Incorrect 79 ms 9304 KB Output isn't correct
12 Runtime error 80 ms 10072 KB Execution killed with signal 13
13 Correct 95 ms 9356 KB Output is correct
14 Incorrect 121 ms 14180 KB Output isn't correct
15 Incorrect 140 ms 18372 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 18836 KB Output isn't correct
2 Incorrect 829 ms 15148 KB Output isn't correct
3 Incorrect 1159 ms 19504 KB Output isn't correct
4 Incorrect 176 ms 10032 KB Output isn't correct
5 Incorrect 234 ms 11956 KB Output isn't correct
6 Correct 518 ms 31648 KB Output is correct
7 Incorrect 752 ms 38488 KB Output isn't correct
8 Incorrect 921 ms 49908 KB Output isn't correct
9 Incorrect 1270 ms 16544 KB Output isn't correct
10 Incorrect 1940 ms 80116 KB Output isn't correct
11 Runtime error 2048 ms 15832 KB Execution killed with signal 13
12 Incorrect 776 ms 49888 KB Output isn't correct
13 Incorrect 1072 ms 50988 KB Output isn't correct
14 Incorrect 1525 ms 57748 KB Output isn't correct
15 Incorrect 1591 ms 71236 KB Output isn't correct
16 Incorrect 1448 ms 82384 KB Output isn't correct
17 Incorrect 1702 ms 73644 KB Output isn't correct