oj.uz

Submission #520200

# Submission time Handle Problem Language Result Execution time Memory
520200 2022-01-28T19:44:24 Z wildturtle Regions (IOI09_regions) C++14
45 / 100
 5641 ms 86592 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,n,ans1,T,q,le,ri,l,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(int, int)':
regions.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 'int' and 'std::vector<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(int, int)':
regions.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 'int' and 'std::vector<std::pair<int, 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: 'int' and 'std::vector<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 28456 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 16 ms 28388 KB Output is correct
4 Correct 20 ms 28488 KB Output is correct
5 Correct 24 ms 28436 KB Output is correct
6 Correct 35 ms 28616 KB Output is correct
7 Correct 51 ms 28616 KB Output is correct
8 Correct 47 ms 28624 KB Output is correct
9 Correct 61 ms 29524 KB Output is correct
10 Correct 110 ms 29516 KB Output is correct
11 Correct 137 ms 30092 KB Output is correct
12 Correct 206 ms 31008 KB Output is correct
13 Correct 244 ms 30992 KB Output is correct
14 Correct 360 ms 31628 KB Output is correct
15 Correct 396 ms 37052 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 89 ms 37944 KB Time limit exceeded (wall clock)
2 Execution timed out 99 ms 37144 KB Time limit exceeded (wall clock)
3 Execution timed out 110 ms 41656 KB Time limit exceeded (wall clock)
4 Correct 337 ms 31852 KB Output is correct
5 Correct 289 ms 35096 KB Output is correct
6 Execution timed out 108 ms 40064 KB Time limit exceeded (wall clock)
7 Correct 1831 ms 36504 KB Output is correct
8 Execution timed out 133 ms 47932 KB Time limit exceeded (wall clock)
9 Correct 2877 ms 46528 KB Output is correct
10 Correct 5149 ms 56492 KB Output is correct
11 Correct 5641 ms 50456 KB Output is correct
12 Execution timed out 245 ms 50028 KB Time limit exceeded (wall clock)
13 Execution timed out 227 ms 51756 KB Time limit exceeded (wall clock)
14 Execution timed out 517 ms 68196 KB Time limit exceeded (wall clock)
15 Execution timed out 238 ms 59688 KB Time limit exceeded (wall clock)
16 Execution timed out 242 ms 72808 KB Time limit exceeded (wall clock)
17 Execution timed out 451 ms 86592 KB Time limit exceeded (wall clock)