oj.uz

Submission #520202

# Submission time Handle Problem Language Result Execution time Memory
520202 2022-01-28T19:49:27 Z wildturtle Regions (IOI09_regions) C++14
100 / 100
 5794 ms 86680 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() {
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    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]<<endl; 
    }
}

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:57: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]
   57 |     for(ll i=0;i<vv.size();i++) {
      |                ~^~~~~~~~~~
regions.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(ll i=0;i<vreg[a].size();i++) {
      |                        ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28488 KB Output is correct
2 Correct 14 ms 28492 KB Output is correct
3 Correct 16 ms 28516 KB Output is correct
4 Correct 18 ms 28488 KB Output is correct
5 Correct 22 ms 28488 KB Output is correct
6 Correct 37 ms 28584 KB Output is correct
7 Correct 32 ms 28616 KB Output is correct
8 Correct 42 ms 28744 KB Output is correct
9 Correct 60 ms 29540 KB Output is correct
10 Correct 98 ms 29472 KB Output is correct
11 Correct 115 ms 30152 KB Output is correct
12 Correct 94 ms 31044 KB Output is correct
13 Correct 222 ms 30992 KB Output is correct
14 Correct 342 ms 31684 KB Output is correct
15 Correct 319 ms 37048 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2302 ms 37956 KB Output is correct
2 Correct 2526 ms 37220 KB Output is correct
3 Correct 3686 ms 41600 KB Output is correct
4 Correct 270 ms 31884 KB Output is correct
5 Correct 352 ms 35128 KB Output is correct
6 Correct 1357 ms 40120 KB Output is correct
7 Correct 1684 ms 36432 KB Output is correct
8 Correct 1564 ms 47932 KB Output is correct
9 Correct 2462 ms 46548 KB Output is correct
10 Correct 5318 ms 56456 KB Output is correct
11 Correct 5794 ms 50428 KB Output is correct
12 Correct 1729 ms 50084 KB Output is correct
13 Correct 2334 ms 51800 KB Output is correct
14 Correct 3119 ms 68128 KB Output is correct
15 Correct 4164 ms 59696 KB Output is correct
16 Correct 4130 ms 72752 KB Output is correct
17 Correct 4006 ms 86680 KB Output is correct