oj.uz

Submission #964744

# Submission time Handle Problem Language Result Execution time Memory
964744 2024-04-17T13:17:33 Z PieArmy Regions (IOI09_regions) C++17
1 / 100
 8000 ms 82528 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];
    }
    return 0;
    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 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++;
        }
        else if(say[renk[i]]<sq){
            fazlapos[renk[i]]=-1;
        }
        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:116:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:116:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 2 ms 12888 KB Output isn't correct
3 Incorrect 4 ms 12728 KB Output isn't correct
4 Incorrect 5 ms 8792 KB Output isn't correct
5 Incorrect 5 ms 8792 KB Output isn't correct
6 Incorrect 10 ms 12888 KB Output isn't correct
7 Incorrect 15 ms 8792 KB Output isn't correct
8 Incorrect 15 ms 8792 KB Output isn't correct
9 Incorrect 23 ms 9304 KB Output isn't correct
10 Incorrect 37 ms 9104 KB Output isn't correct
11 Incorrect 47 ms 9360 KB Output isn't correct
12 Incorrect 60 ms 9780 KB Output isn't correct
13 Incorrect 81 ms 9348 KB Output isn't correct
14 Incorrect 94 ms 14140 KB Output isn't correct
15 Incorrect 96 ms 18496 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 508 ms 18860 KB Output isn't correct
2 Incorrect 533 ms 15208 KB Output isn't correct
3 Incorrect 724 ms 19524 KB Output isn't correct
4 Incorrect 651 ms 20476 KB Output isn't correct
5 Incorrect 1980 ms 25168 KB Output isn't correct
6 Incorrect 2618 ms 31420 KB Output isn't correct
7 Incorrect 680 ms 38508 KB Output isn't correct
8 Incorrect 821 ms 50080 KB Output isn't correct
9 Execution timed out 8057 ms 45636 KB Time limit exceeded
10 Execution timed out 8047 ms 77708 KB Time limit exceeded
11 Execution timed out 8039 ms 57556 KB Time limit exceeded
12 Execution timed out 8026 ms 47764 KB Time limit exceeded
13 Execution timed out 8102 ms 48648 KB Time limit exceeded
14 Execution timed out 8007 ms 53472 KB Time limit exceeded
15 Incorrect 1025 ms 71180 KB Output isn't correct
16 Incorrect 1222 ms 82528 KB Output isn't correct
17 Execution timed out 8038 ms 71616 KB Time limit exceeded