oj.uz

Submission #492261

# Submission time Handle Problem Language Result Execution time Memory
492261 2021-12-06T10:10:52 Z lukameladze Regions (IOI09_regions) C++14
100 / 100
 6419 ms 57892 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5, B = 500;
int tin,in[N],out[N],r1,r2,fer,n,le,ri,up,hea[N],lig[N],col[N],r,q,p[N],idx[N];
multiset <pii> :: iterator it;
int mpp[N],shes[N];
long long ans[550][30000],anss;
vector <int> heavy,light;
vector <int> v[N],v1[N];
multiset <pii> ms[N];
vector <pii> vv;
multiset <int> mss;
void dfs(int a, int p) {
    tin++;
    in[a] = tin;
    vv.pb({in[a],a});
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs(to,a);
    }
    out[a] = tin;
}
void dfs1(int a, int p) {
    if (hea[col[a]]) {
        mpp[col[a]]++;
    }
    for (int j = 0; j < heavy.size(); j++) {
        fer = heavy[j];
        if (mpp[fer]) ans[shes[fer]][col[a]]+= mpp[fer];
    }
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs1(to,a);
    }
    if (hea[col[a]]) mpp[col[a]]--;
}
main() {
    cin>>n>>r>>q;
    for (int i = 1; i <= n; i++) {
       if (i != 1) cin>>p[i],v[p[i]].pb(i),v[i].pb(p[i]);
        cin>>col[i];
        v1[col[i]].pb(i);
    }
    for (int i = 1; i <= r; i++) {
        if (v1[i].size() >= B) heavy.pb(i), hea[i] = 1;
        else light.pb(i),lig[i] = 1;
    }
    for (int j = 0; j < heavy.size(); j++) {
    	shes[heavy[j]] = j;
	}
      dfs(1,0);
      sort(vv.begin(),vv.end());
    for (int i = 0; i < vv.size(); i++) {
        idx[col[vv[i].s]]++;
        ms[col[vv[i].s]].insert({vv[i].f,idx[col[vv[i].s]]});
    }
    dfs1(1,0);
    while(q--) {
        cin>>r1>>r2;
        if (lig[r1]) {
            int anss = 0;
            for (int i = 0; i < v1[r1].size(); i++) {
                up = v1[r1][i];
                it = ms[r2].lower_bound({in[up],0});
                if (it == ms[r2].end()) continue;
                le = (*it).s;
                it = ms[r2].upper_bound({out[up],1e9});
                if (it == ms[r2].end()) ri = ms[r2].size();
                else ri = (*it).s - 1;
                anss += (ri - le + 1);
            }
            cout<<anss<<"\n";
            continue;
        }
        cout<<ans[shes[r1]][r2]<<"\n";
    }
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(int, int)':
regions.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
regions.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (int i = 0; i < v1[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19016 KB Output is correct
2 Correct 11 ms 19092 KB Output is correct
3 Correct 12 ms 19016 KB Output is correct
4 Correct 15 ms 19016 KB Output is correct
5 Correct 13 ms 19144 KB Output is correct
6 Correct 29 ms 19212 KB Output is correct
7 Correct 38 ms 19272 KB Output is correct
8 Correct 45 ms 19248 KB Output is correct
9 Correct 59 ms 20044 KB Output is correct
10 Correct 95 ms 20132 KB Output is correct
11 Correct 136 ms 20808 KB Output is correct
12 Correct 193 ms 21624 KB Output is correct
13 Correct 206 ms 21692 KB Output is correct
14 Correct 367 ms 22376 KB Output is correct
15 Correct 404 ms 26528 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2422 ms 28388 KB Output is correct
2 Correct 2550 ms 28060 KB Output is correct
3 Correct 3631 ms 31532 KB Output is correct
4 Correct 325 ms 22596 KB Output is correct
5 Correct 470 ms 25180 KB Output is correct
6 Correct 1502 ms 26444 KB Output is correct
7 Correct 1886 ms 27204 KB Output is correct
8 Correct 1611 ms 35636 KB Output is correct
9 Correct 2996 ms 37296 KB Output is correct
10 Correct 5771 ms 45008 KB Output is correct
11 Correct 6419 ms 41780 KB Output is correct
12 Correct 1801 ms 40364 KB Output is correct
13 Correct 2877 ms 41548 KB Output is correct
14 Correct 3019 ms 45416 KB Output is correct
15 Correct 4757 ms 47256 KB Output is correct
16 Correct 4540 ms 56388 KB Output is correct
17 Correct 4115 ms 57892 KB Output is correct