oj.uz

Submission #964741

# Submission time Handle Problem Language Result Execution time Memory
964741 2024-04-17T13:01:19 Z PieArmy Regions (IOI09_regions) C++17
8 / 100
 8000 ms 82400 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];
    }
    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: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 5 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Incorrect 4 ms 12888 KB Output isn't correct
4 Incorrect 4 ms 8792 KB Output isn't correct
5 Incorrect 5 ms 8792 KB Output isn't correct
6 Incorrect 12 ms 12888 KB Output isn't correct
7 Incorrect 17 ms 8800 KB Output isn't correct
8 Incorrect 17 ms 8792 KB Output isn't correct
9 Incorrect 31 ms 9304 KB Output isn't correct
10 Incorrect 49 ms 9048 KB Output isn't correct
11 Incorrect 70 ms 9304 KB Output isn't correct
12 Incorrect 97 ms 9848 KB Output isn't correct
13 Correct 112 ms 9812 KB Output is correct
14 Incorrect 145 ms 14168 KB Output isn't correct
15 Incorrect 148 ms 18452 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 709 ms 18856 KB Output isn't correct
2 Incorrect 771 ms 15204 KB Output isn't correct
3 Incorrect 1248 ms 19456 KB Output isn't correct
4 Incorrect 694 ms 20484 KB Output isn't correct
5 Runtime error 2138 ms 25172 KB Execution killed with signal 13
6 Correct 2493 ms 31664 KB Output is correct
7 Incorrect 720 ms 38508 KB Output isn't correct
8 Incorrect 871 ms 50132 KB Output isn't correct
9 Execution timed out 8012 ms 45756 KB Time limit exceeded
10 Execution timed out 8039 ms 77960 KB Time limit exceeded
11 Execution timed out 8026 ms 57764 KB Time limit exceeded
12 Execution timed out 8077 ms 47812 KB Time limit exceeded
13 Execution timed out 8076 ms 48704 KB Time limit exceeded
14 Execution timed out 8041 ms 53660 KB Time limit exceeded
15 Runtime error 1746 ms 71412 KB Execution killed with signal 13
16 Incorrect 1660 ms 82400 KB Output isn't correct
17 Execution timed out 8053 ms 71616 KB Time limit exceeded