oj.uz

Submission #520199

# Submission time Handle Problem Language Result Execution time Memory
520199 2022-01-28T19:33:05 Z wildturtle Regions (IOI09_regions) C++14
45 / 100
 7778 ms 100964 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(vreg[a].size()<500) {
            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,1e9});
                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;
        } else cout<<ans[a][b]; 
    }
}

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:25: 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 28488 KB Output is correct
2 Correct 14 ms 28432 KB Output is correct
3 Correct 16 ms 28488 KB Output is correct
4 Correct 16 ms 28488 KB Output is correct
5 Correct 22 ms 28488 KB Output is correct
6 Correct 28 ms 28616 KB Output is correct
7 Correct 42 ms 28616 KB Output is correct
8 Correct 47 ms 28744 KB Output is correct
9 Correct 58 ms 29740 KB Output is correct
10 Correct 86 ms 30008 KB Output is correct
11 Correct 155 ms 30760 KB Output is correct
12 Correct 152 ms 31812 KB Output is correct
13 Correct 253 ms 32192 KB Output is correct
14 Correct 360 ms 32988 KB Output is correct
15 Correct 358 ms 38836 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 90 ms 40940 KB Time limit exceeded (wall clock)
2 Execution timed out 101 ms 40760 KB Time limit exceeded (wall clock)
3 Execution timed out 110 ms 45384 KB Time limit exceeded (wall clock)
4 Correct 273 ms 33208 KB Output is correct
5 Correct 427 ms 36680 KB Output is correct
6 Execution timed out 112 ms 44168 KB Time limit exceeded (wall clock)
7 Correct 1995 ms 39508 KB Output is correct
8 Execution timed out 138 ms 52468 KB Time limit exceeded (wall clock)
9 Correct 3170 ms 52924 KB Output is correct
10 Correct 6608 ms 63360 KB Output is correct
11 Correct 7778 ms 59356 KB Output is correct
12 Execution timed out 264 ms 58184 KB Time limit exceeded (wall clock)
13 Execution timed out 243 ms 60196 KB Time limit exceeded (wall clock)
14 Execution timed out 516 ms 82612 KB Time limit exceeded (wall clock)
15 Execution timed out 299 ms 68468 KB Time limit exceeded (wall clock)
16 Execution timed out 251 ms 81400 KB Time limit exceeded (wall clock)
17 Execution timed out 492 ms 100964 KB Time limit exceeded (wall clock)