oj.uz

Submission #964750

# Submission time Handle Problem Language Result Execution time Memory
964750 2024-04-17T13:27:44 Z PieArmy Regions (IOI09_regions) C++17
2 / 100
 2015 ms 29580 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*/true)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:117:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:117:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8836 KB Output isn't correct
2 Correct 2 ms 8792 KB Output is correct
3 Incorrect 2 ms 8792 KB Output isn't correct
4 Incorrect 4 ms 8952 KB Output isn't correct
5 Incorrect 6 ms 8792 KB Output isn't correct
6 Incorrect 11 ms 8792 KB Output isn't correct
7 Incorrect 16 ms 8792 KB Output isn't correct
8 Incorrect 19 ms 8792 KB Output isn't correct
9 Incorrect 26 ms 9304 KB Output isn't correct
10 Incorrect 42 ms 9284 KB Output isn't correct
11 Incorrect 63 ms 9304 KB Output isn't correct
12 Incorrect 82 ms 10092 KB Output isn't correct
13 Correct 93 ms 9560 KB Output is correct
14 Incorrect 125 ms 10364 KB Output isn't correct
15 Incorrect 131 ms 13156 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 596 ms 12680 KB Execution killed with signal 13
2 Incorrect 639 ms 11320 KB Output isn't correct
3 Incorrect 1070 ms 14388 KB Output isn't correct
4 Incorrect 158 ms 10032 KB Output isn't correct
5 Incorrect 220 ms 11864 KB Output isn't correct
6 Incorrect 329 ms 11244 KB Output isn't correct
7 Incorrect 517 ms 12440 KB Output isn't correct
8 Incorrect 503 ms 17260 KB Output isn't correct
9 Incorrect 1253 ms 16800 KB Output isn't correct
10 Incorrect 1141 ms 22356 KB Output isn't correct
11 Incorrect 2015 ms 15860 KB Output isn't correct
12 Incorrect 690 ms 17568 KB Output isn't correct
13 Incorrect 1016 ms 17548 KB Output isn't correct
14 Incorrect 1034 ms 16928 KB Output isn't correct
15 Incorrect 1567 ms 22896 KB Output isn't correct
16 Incorrect 1372 ms 29580 KB Output isn't correct
17 Incorrect 1417 ms 28180 KB Output isn't correct