oj.uz

Submission #492262

# Submission time Handle Problem Language Result Execution time Memory
492262 2021-12-06T10:13:09 Z lukameladze Regions (IOI09_regions) C++14
100 / 100
 7719 ms 100212 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5, B = 500;
int tin,in[N],out[N],anss,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];
map <int,int> ans[N];
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[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[r1][r2]<<"\n";
    }
}

Compilation message

regions.cpp: In function 'void dfs(long long int, long long int)':
regions.cpp:22:23: 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]
   22 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(long long int, long long int)':
regions.cpp:33:23: 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]
   33 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:37:23: 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]
   37 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:55:23: 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]
   55 |     for (int j = 0; j < heavy.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~
regions.cpp:60:23: 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]
   60 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
regions.cpp:69:31: 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]
   69 |             for (int i = 0; i < v1[r1].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28488 KB Output is correct
2 Correct 13 ms 28484 KB Output is correct
3 Correct 15 ms 28436 KB Output is correct
4 Correct 19 ms 28448 KB Output is correct
5 Correct 24 ms 28500 KB Output is correct
6 Correct 32 ms 28656 KB Output is correct
7 Correct 44 ms 28676 KB Output is correct
8 Correct 46 ms 28744 KB Output is correct
9 Correct 69 ms 29692 KB Output is correct
10 Correct 97 ms 30032 KB Output is correct
11 Correct 158 ms 30924 KB Output is correct
12 Correct 133 ms 32028 KB Output is correct
13 Correct 232 ms 32364 KB Output is correct
14 Correct 342 ms 33176 KB Output is correct
15 Correct 400 ms 38356 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2346 ms 41388 KB Output is correct
2 Correct 3114 ms 41264 KB Output is correct
3 Correct 4233 ms 45496 KB Output is correct
4 Correct 311 ms 33544 KB Output is correct
5 Correct 359 ms 36624 KB Output is correct
6 Correct 1428 ms 44704 KB Output is correct
7 Correct 2250 ms 40008 KB Output is correct
8 Correct 1767 ms 52288 KB Output is correct
9 Correct 3256 ms 53952 KB Output is correct
10 Correct 6190 ms 63452 KB Output is correct
11 Correct 7719 ms 61100 KB Output is correct
12 Correct 2490 ms 59800 KB Output is correct
13 Correct 3038 ms 61456 KB Output is correct
14 Correct 4049 ms 84388 KB Output is correct
15 Correct 4877 ms 69236 KB Output is correct
16 Correct 4922 ms 80208 KB Output is correct
17 Correct 5033 ms 100212 KB Output is correct