oj.uz

Submission #964846

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12724 KB Output isn't correct
2 Incorrect 2 ms 8792 KB Output isn't correct
3 Incorrect 2 ms 8792 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 11 ms 8792 KB Output isn't correct
7 Incorrect 14 ms 8792 KB Output isn't correct
8 Incorrect 17 ms 8792 KB Output isn't correct
9 Incorrect 29 ms 9304 KB Output isn't correct
10 Incorrect 49 ms 9036 KB Output isn't correct
11 Incorrect 53 ms 9304 KB Output isn't correct
12 Incorrect 64 ms 9824 KB Output isn't correct
13 Incorrect 81 ms 9520 KB Output isn't correct
14 Incorrect 83 ms 14168 KB Output isn't correct
15 Incorrect 89 ms 18308 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 18864 KB Output isn't correct
2 Incorrect 507 ms 15200 KB Output isn't correct
3 Incorrect 745 ms 19452 KB Output isn't correct
4 Incorrect 122 ms 10060 KB Output isn't correct
5 Incorrect 196 ms 12084 KB Output isn't correct
6 Incorrect 461 ms 27416 KB Output isn't correct
7 Incorrect 607 ms 31784 KB Output isn't correct
8 Incorrect 826 ms 41188 KB Output isn't correct
9 Incorrect 714 ms 16804 KB Output isn't correct
10 Incorrect 1719 ms 78496 KB Output isn't correct
11 Incorrect 1050 ms 15864 KB Output isn't correct
12 Incorrect 614 ms 46156 KB Output isn't correct
13 Incorrect 706 ms 47868 KB Output isn't correct
14 Incorrect 1386 ms 53952 KB Output isn't correct
15 Incorrect 1039 ms 70292 KB Output isn't correct
16 Incorrect 1091 ms 81356 KB Output isn't correct
17 Incorrect 1274 ms 70700 KB Output isn't correct