oj.uz

Submission #520197

# Submission time Handle Problem Language Result Execution time Memory
520197 2022-01-28T19:23:39 Z wildturtle Regions (IOI09_regions) C++14
45 / 100
 7785 ms 100908 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,ans1,T,q,le,ri,r,t,rr,p;
ll fix[200005],mp[200005],in[200005],out[200005],mdzime[200005],reg[200005],regsz[200005];
map <ll,ll> ans[200005];
vector <ll> v[200005],v1,vreg[200005];
vector < pair <ll,ll> > vv;
multiset < pair <ll,ll> > ms[200005];
multiset < pair <ll,ll> >::iterator it;
void dfs(ll x,ll y) {
    if(mdzime[reg[x]]) mp[reg[x]]++;
    for(ll i=0;i<v1.size();i++) {
        ans[v1[i]][reg[x]]+=mp[v1[i]];
    }
    for(ll i=0;i<v[x].size();i++) {
        if(v[x][i]==y) continue;
        dfs(v[x][i],x);
    }
    if(mdzime[reg[x]]) mp[reg[x]]--;
}
void dfs1(ll x,ll y) {
    T++;
    in[x]=T;
    vv.pb({in[x],reg[x]});
    for(ll i=0;i<v[x].size();i++) {
        if(v[x][i]==y) continue;
        dfs1(v[x][i],x);
    }
    out[x]=T;
}
int main() {
    cin>>n>>r>>t;
    for(ll i=1;i<=n;i++) {
        if(i!=1) {
            cin>>p;
            v[i].pb(p); 
            v[p].pb(i);
        }
        cin>>reg[i];
        regsz[reg[i]]++;
        vreg[reg[i]].pb(i);
    }
    for(ll i=1;i<=r;i++) {
        if(regsz[i]>=500) {
            mdzime[i]=1;
            v1.pb(i);
        }
    }
    dfs(1,0);
    dfs1(1,0);
    sort(vv.begin(),vv.end());
    for(ll i=0;i<vv.size();i++) {
        //cout<<vv[i].f<<" "<<vv[i].sc<<endl;
        
        fix[vv[i].sc]++;
        ms[vv[i].sc].insert({vv[i].f,fix[vv[i].sc]});
    }
    //cout<<endl;
    while(t--) {
        cin>>a>>b;
        if(ans[a][b]) { cout<<ans[a][b]; continue; }
        for(ll i=0;i<vreg[a].size();i++) {
            le=in[vreg[a][i]]; ri=out[vreg[a][i]];
            //cout<<vreg[a][i]<<" "<<le<<" "<<ri<<endl;
            it=ms[b].lower_bound({le,0});
            if(it==ms[b].end()) continue;
            l=(*it).sc;
            it=ms[b].lower_bound({ri,1e18});
            if(it==ms[b].end()) rr=ms[b].size();
            else rr=(*it).sc-1;    
            //cout<<l<<"_"<<rr<<endl;
            ans1+=rr-l+1;
        }
        cout<<ans1<<endl;
        ans1=0;
    }
}

Compilation message

regions.cpp: In function 'void dfs(long long int, long long int)':
regions.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(ll i=0;i<v1.size();i++) {
      |                ~^~~~~~~~~~
regions.cpp:19:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(ll i=0;i<v[x].size();i++) {
      |                ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs1(long long int, long long int)':
regions.cpp:29:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(ll i=0;i<v[x].size();i++) {
      |                ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(ll i=0;i<vv.size();i++) {
      |                ~^~~~~~~~~~
regions.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(ll i=0;i<vreg[a].size();i++) {
      |                    ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28540 KB Output is correct
2 Correct 15 ms 28456 KB Output is correct
3 Correct 15 ms 28512 KB Output is correct
4 Correct 18 ms 28492 KB Output is correct
5 Correct 19 ms 28620 KB Output is correct
6 Correct 22 ms 28776 KB Output is correct
7 Correct 39 ms 28892 KB Output is correct
8 Correct 49 ms 28904 KB Output is correct
9 Correct 73 ms 30076 KB Output is correct
10 Correct 104 ms 30512 KB Output is correct
11 Correct 139 ms 31428 KB Output is correct
12 Correct 180 ms 32708 KB Output is correct
13 Correct 242 ms 32944 KB Output is correct
14 Correct 372 ms 33844 KB Output is correct
15 Correct 322 ms 39684 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 95 ms 40980 KB Time limit exceeded (wall clock)
2 Execution timed out 106 ms 40764 KB Time limit exceeded (wall clock)
3 Execution timed out 106 ms 45328 KB Time limit exceeded (wall clock)
4 Correct 329 ms 34716 KB Output is correct
5 Correct 496 ms 38836 KB Output is correct
6 Execution timed out 109 ms 44100 KB Time limit exceeded (wall clock)
7 Correct 1907 ms 41064 KB Output is correct
8 Execution timed out 130 ms 52384 KB Time limit exceeded (wall clock)
9 Correct 4043 ms 61192 KB Output is correct
10 Correct 7785 ms 73472 KB Output is correct
11 Correct 7676 ms 71460 KB Output is correct
12 Execution timed out 259 ms 58160 KB Time limit exceeded (wall clock)
13 Execution timed out 244 ms 60176 KB Time limit exceeded (wall clock)
14 Execution timed out 511 ms 82760 KB Time limit exceeded (wall clock)
15 Execution timed out 271 ms 68540 KB Time limit exceeded (wall clock)
16 Execution timed out 260 ms 81524 KB Time limit exceeded (wall clock)
17 Execution timed out 497 ms 100908 KB Time limit exceeded (wall clock)