oj.uz

Submission #964875

# Submission time Handle Problem Language Result Execution time Memory
964875 2024-04-17T16:51:30 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 1985 ms 82504 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){
        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 8620 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 19 ms 8792 KB Output isn't correct
8 Incorrect 16 ms 8792 KB Output isn't correct
9 Incorrect 29 ms 9140 KB Output isn't correct
10 Incorrect 42 ms 9048 KB Output isn't correct
11 Incorrect 65 ms 9304 KB Output isn't correct
12 Incorrect 87 ms 9956 KB Output isn't correct
13 Correct 91 ms 9404 KB Output is correct
14 Incorrect 136 ms 14000 KB Output isn't correct
15 Incorrect 129 ms 18364 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 18784 KB Output isn't correct
2 Incorrect 767 ms 15016 KB Output isn't correct
3 Incorrect 1159 ms 19528 KB Output isn't correct
4 Incorrect 152 ms 9972 KB Output isn't correct
5 Incorrect 218 ms 11808 KB Output isn't correct
6 Correct 487 ms 31644 KB Output is correct
7 Incorrect 751 ms 38484 KB Output isn't correct
8 Incorrect 914 ms 50112 KB Output isn't correct
9 Incorrect 1204 ms 16912 KB Output isn't correct
10 Incorrect 1936 ms 79992 KB Output isn't correct
11 Incorrect 1985 ms 15640 KB Output isn't correct
12 Incorrect 824 ms 49960 KB Output isn't correct
13 Incorrect 1078 ms 50844 KB Output isn't correct
14 Incorrect 1457 ms 57748 KB Output isn't correct
15 Incorrect 1623 ms 71236 KB Output isn't correct
16 Incorrect 1473 ms 82504 KB Output isn't correct
17 Incorrect 1718 ms 73644 KB Output isn't correct