oj.uz

Submission #964730

# Submission time Handle Problem Language Result Execution time Memory
964730 2024-04-17T12:15:41 Z PieArmy Regions (IOI09_regions) C++17
3 / 100
 8000 ms 79856 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],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]];
    }
    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;
    };
    for(int i=1;i<=R;i++){
        if(fazlapos[i]==-1)continue;
        f(1,i);
    }
    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++){
        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:101:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:101:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     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 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Incorrect 3 ms 10840 KB Output isn't correct
4 Incorrect 4 ms 8792 KB Output isn't correct
5 Incorrect 6 ms 8792 KB Output isn't correct
6 Incorrect 12 ms 10840 KB Output isn't correct
7 Incorrect 18 ms 9036 KB Output isn't correct
8 Incorrect 17 ms 8792 KB Output isn't correct
9 Incorrect 28 ms 9300 KB Output isn't correct
10 Incorrect 44 ms 9068 KB Output isn't correct
11 Incorrect 67 ms 9448 KB Output isn't correct
12 Incorrect 91 ms 9856 KB Output isn't correct
13 Correct 93 ms 9480 KB Output is correct
14 Incorrect 152 ms 12108 KB Output isn't correct
15 Incorrect 136 ms 16272 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1666 ms 15368 KB Execution killed with signal 13
2 Runtime error 1872 ms 13576 KB Execution killed with signal 13
3 Runtime error 2294 ms 17944 KB Execution killed with signal 13
4 Incorrect 457 ms 18432 KB Output isn't correct
5 Incorrect 1262 ms 23120 KB Output isn't correct
6 Incorrect 1608 ms 25776 KB Output isn't correct
7 Incorrect 812 ms 30552 KB Output isn't correct
8 Incorrect 857 ms 38272 KB Output isn't correct
9 Execution timed out 8048 ms 43868 KB Time limit exceeded
10 Execution timed out 8052 ms 69328 KB Time limit exceeded
11 Execution timed out 8096 ms 56672 KB Time limit exceeded
12 Execution timed out 8003 ms 43648 KB Time limit exceeded
13 Execution timed out 8099 ms 44452 KB Time limit exceeded
14 Execution timed out 8025 ms 51540 KB Time limit exceeded
15 Runtime error 4104 ms 68892 KB Execution killed with signal 13
16 Runtime error 4386 ms 79856 KB Execution killed with signal 13
17 Execution timed out 8085 ms 67384 KB Time limit exceeded