oj.uz

Submission #964746

# Submission time Handle Problem Language Result Execution time Memory
964746 2024-04-17T13:21:38 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 2318 ms 82332 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];
    }
    stack<int>sta;
    int apos=0;
    int ans=0;
    for(int i=say[b]-1;i>=0;i--){
        while(sta.size()&&bas[sta.top()]>bas[var[b][i]]){
            sta.pop();
        }
        while(apos<say[a]&&son[sirali[a][apos]]>=bas[var[b][i]]){
            if(bas[sirali[a][apos]]<=bas[var[b][i]])
                sta.push(sirali[a][apos]);
            apos++;
        }
        ans+=sta.size();
    }
    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(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    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: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
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 3 ms 8792 KB Output isn't correct
4 Incorrect 4 ms 8628 KB Output isn't correct
5 Incorrect 4 ms 8792 KB Output isn't correct
6 Incorrect 11 ms 8792 KB Output isn't correct
7 Incorrect 14 ms 8792 KB Output isn't correct
8 Incorrect 19 ms 8792 KB Output isn't correct
9 Incorrect 26 ms 9376 KB Output isn't correct
10 Incorrect 50 ms 9048 KB Output isn't correct
11 Incorrect 72 ms 9304 KB Output isn't correct
12 Incorrect 86 ms 9816 KB Output isn't correct
13 Correct 92 ms 9560 KB Output is correct
14 Incorrect 153 ms 14168 KB Output isn't correct
15 Incorrect 149 ms 18260 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 714 ms 19016 KB Execution killed with signal 13
2 Incorrect 776 ms 15200 KB Output isn't correct
3 Runtime error 1237 ms 19596 KB Execution killed with signal 13
4 Incorrect 162 ms 10264 KB Output isn't correct
5 Incorrect 238 ms 11888 KB Output isn't correct
6 Correct 489 ms 31672 KB Output is correct
7 Incorrect 645 ms 38672 KB Output isn't correct
8 Incorrect 928 ms 50036 KB Output isn't correct
9 Incorrect 1420 ms 16984 KB Output isn't correct
10 Incorrect 1960 ms 80072 KB Output isn't correct
11 Incorrect 2318 ms 15852 KB Output isn't correct
12 Incorrect 810 ms 49864 KB Output isn't correct
13 Incorrect 1088 ms 50916 KB Output isn't correct
14 Incorrect 1689 ms 57924 KB Output isn't correct
15 Incorrect 1677 ms 71308 KB Output isn't correct
16 Incorrect 1521 ms 82332 KB Output isn't correct
17 Runtime error 1878 ms 73840 KB Execution killed with signal 13