oj.uz

Submission #964857

# Submission time Handle Problem Language Result Execution time Memory
964857 2024-04-17T16:37:54 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 1931 ms 82712 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{
        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:115:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:115:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     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 8792 KB Output is correct
3 Incorrect 4 ms 8792 KB Output isn't correct
4 Incorrect 3 ms 8792 KB Output isn't correct
5 Incorrect 5 ms 8792 KB Output isn't correct
6 Incorrect 12 ms 8792 KB Output isn't correct
7 Incorrect 18 ms 8792 KB Output isn't correct
8 Incorrect 16 ms 8836 KB Output isn't correct
9 Incorrect 21 ms 9304 KB Output isn't correct
10 Incorrect 54 ms 9048 KB Output isn't correct
11 Incorrect 61 ms 9332 KB Output isn't correct
12 Incorrect 84 ms 9940 KB Output isn't correct
13 Correct 104 ms 9436 KB Output is correct
14 Incorrect 129 ms 14184 KB Output isn't correct
15 Incorrect 124 ms 18344 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 19456 KB Output isn't correct
2 Incorrect 759 ms 15600 KB Output isn't correct
3 Runtime error 1097 ms 19984 KB Execution killed with signal 13
4 Incorrect 142 ms 10036 KB Output isn't correct
5 Incorrect 203 ms 12120 KB Output isn't correct
6 Correct 469 ms 31808 KB Output is correct
7 Incorrect 629 ms 38740 KB Output isn't correct
8 Incorrect 903 ms 50640 KB Output isn't correct
9 Runtime error 1141 ms 16804 KB Execution killed with signal 13
10 Incorrect 1931 ms 80532 KB Output isn't correct
11 Runtime error 1870 ms 16132 KB Execution killed with signal 13
12 Incorrect 747 ms 50148 KB Output isn't correct
13 Incorrect 1025 ms 51168 KB Output isn't correct
14 Incorrect 1429 ms 58556 KB Output isn't correct
15 Incorrect 1503 ms 71872 KB Output isn't correct
16 Incorrect 1438 ms 82712 KB Output isn't correct
17 Incorrect 1662 ms 74536 KB Output isn't correct