oj.uz

Submission #964845

# Submission time Handle Problem Language Result Execution time Memory
964845 2024-04-17T16:10:51 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 2024 ms 81432 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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 2 ms 8788 KB Output is correct
3 Incorrect 5 ms 8792 KB Output isn't correct
4 Incorrect 5 ms 8792 KB Output isn't correct
5 Incorrect 9 ms 8792 KB Output isn't correct
6 Incorrect 11 ms 8792 KB Output isn't correct
7 Incorrect 21 ms 8792 KB Output isn't correct
8 Incorrect 21 ms 8792 KB Output isn't correct
9 Incorrect 28 ms 9308 KB Output isn't correct
10 Incorrect 48 ms 9056 KB Output isn't correct
11 Incorrect 66 ms 9488 KB Output isn't correct
12 Incorrect 84 ms 9816 KB Output isn't correct
13 Correct 90 ms 9404 KB Output is correct
14 Incorrect 153 ms 14024 KB Output isn't correct
15 Incorrect 117 ms 18264 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 654 ms 18860 KB Output isn't correct
2 Incorrect 729 ms 15208 KB Output isn't correct
3 Incorrect 1145 ms 19516 KB Output isn't correct
4 Incorrect 164 ms 10196 KB Output isn't correct
5 Incorrect 217 ms 11976 KB Output isn't correct
6 Correct 463 ms 27340 KB Output is correct
7 Incorrect 669 ms 31636 KB Output isn't correct
8 Incorrect 917 ms 42208 KB Output isn't correct
9 Incorrect 1188 ms 16832 KB Output isn't correct
10 Incorrect 2001 ms 78644 KB Output isn't correct
11 Runtime error 2024 ms 15948 KB Execution killed with signal 13
12 Incorrect 711 ms 46216 KB Output isn't correct
13 Incorrect 1012 ms 47888 KB Output isn't correct
14 Runtime error 1543 ms 54016 KB Execution killed with signal 13
15 Runtime error 1505 ms 70432 KB Execution killed with signal 13
16 Incorrect 1430 ms 81432 KB Output isn't correct
17 Incorrect 1758 ms 69892 KB Output isn't correct