oj.uz

Submission #964751

# Submission time Handle Problem Language Result Execution time Memory
964751 2024-04-17T13:29:00 Z PieArmy Regions (IOI09_regions) C++17
2 / 100
 2020 ms 82400 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(){
    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 10840 KB Output isn't correct
2 Correct 2 ms 8792 KB Output is correct
3 Incorrect 3 ms 8792 KB Output isn't correct
4 Incorrect 3 ms 8792 KB Output isn't correct
5 Incorrect 7 ms 8792 KB Output isn't correct
6 Incorrect 11 ms 8792 KB Output isn't correct
7 Incorrect 18 ms 8792 KB Output isn't correct
8 Incorrect 21 ms 8792 KB Output isn't correct
9 Incorrect 32 ms 9304 KB Output isn't correct
10 Incorrect 45 ms 9048 KB Output isn't correct
11 Incorrect 59 ms 9304 KB Output isn't correct
12 Incorrect 85 ms 9772 KB Output isn't correct
13 Correct 102 ms 9560 KB Output is correct
14 Incorrect 124 ms 12180 KB Output isn't correct
15 Incorrect 130 ms 16472 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 626 ms 14912 KB Output isn't correct
2 Incorrect 686 ms 13172 KB Output isn't correct
3 Incorrect 1096 ms 17768 KB Output isn't correct
4 Incorrect 164 ms 10328 KB Output isn't correct
5 Incorrect 232 ms 11908 KB Output isn't correct
6 Incorrect 423 ms 25516 KB Output isn't correct
7 Incorrect 608 ms 32580 KB Output isn't correct
8 Incorrect 712 ms 39900 KB Output isn't correct
9 Runtime error 1205 ms 16804 KB Execution killed with signal 13
10 Incorrect 1591 ms 71992 KB Output isn't correct
11 Incorrect 2020 ms 15856 KB Output isn't correct
12 Runtime error 763 ms 48140 KB Execution killed with signal 13
13 Incorrect 958 ms 48872 KB Output isn't correct
14 Incorrect 1415 ms 55876 KB Output isn't correct
15 Runtime error 1574 ms 71408 KB Execution killed with signal 13
16 Incorrect 1384 ms 82400 KB Output isn't correct
17 Runtime error 1598 ms 71792 KB Execution killed with signal 13