oj.uz

Submission #492119

# Submission time Handle Problem Language Result Execution time Memory
492119 2021-12-05T14:16:52 Z lukameladze Regions (IOI09_regions) C++14
95 / 100
 7803 ms 131076 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
#define int long long
using namespace std;
const int N = 2e5 + 5, B = 400;
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];
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 (fer == 1 && col[a] == 3)
        //cout<<fer<<" "<<a<<" "<<col[a]<<endl;
        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;
    }
      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:39: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]
   39 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main() {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:59: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]
   59 |     for (int i = 0; i < vv.size(); i++) {
      |                     ~~^~~~~~~~~~~
regions.cpp:68: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]
   68 |             for (int i = 0; i < v1[r1].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 16 ms 28512 KB Output is correct
3 Correct 17 ms 28472 KB Output is correct
4 Correct 20 ms 28436 KB Output is correct
5 Correct 24 ms 28528 KB Output is correct
6 Correct 39 ms 28616 KB Output is correct
7 Correct 45 ms 28744 KB Output is correct
8 Correct 33 ms 28872 KB Output is correct
9 Correct 59 ms 29768 KB Output is correct
10 Correct 117 ms 30124 KB Output is correct
11 Correct 171 ms 30880 KB Output is correct
12 Correct 187 ms 31960 KB Output is correct
13 Correct 248 ms 32308 KB Output is correct
14 Correct 359 ms 33180 KB Output is correct
15 Correct 466 ms 38324 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2526 ms 41476 KB Output is correct
2 Correct 2647 ms 41264 KB Output is correct
3 Correct 4046 ms 45452 KB Output is correct
4 Correct 337 ms 33464 KB Output is correct
5 Correct 475 ms 36608 KB Output is correct
6 Correct 1000 ms 60404 KB Output is correct
7 Correct 2151 ms 57004 KB Output is correct
8 Correct 3092 ms 113268 KB Output is correct
9 Correct 3388 ms 53924 KB Output is correct
10 Runtime error 1833 ms 131076 KB Execution killed with signal 9
11 Correct 7803 ms 61096 KB Output is correct
12 Correct 2574 ms 59740 KB Output is correct
13 Correct 3075 ms 61552 KB Output is correct
14 Correct 4167 ms 84404 KB Output is correct
15 Correct 5249 ms 69156 KB Output is correct
16 Correct 4734 ms 80276 KB Output is correct
17 Correct 4997 ms 100124 KB Output is correct