oj.uz

Submission #492121

# Submission time Handle Problem Language Result Execution time Memory
492121 2021-12-05T14:25:33 Z lukameladze Regions (IOI09_regions) C++14
95 / 100
 7626 ms 131072 KB 
# include <bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pb push_back
#define pii pair <long long, long long>
using namespace std;
const int N = 3e5 + 5, B = 450;
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 22 ms 42564 KB Output is correct
2 Correct 23 ms 42532 KB Output is correct
3 Correct 24 ms 42568 KB Output is correct
4 Correct 33 ms 42572 KB Output is correct
5 Correct 30 ms 42696 KB Output is correct
6 Correct 40 ms 42688 KB Output is correct
7 Correct 61 ms 42824 KB Output is correct
8 Correct 54 ms 42952 KB Output is correct
9 Correct 63 ms 43848 KB Output is correct
10 Correct 100 ms 44100 KB Output is correct
11 Correct 164 ms 44860 KB Output is correct
12 Correct 199 ms 46112 KB Output is correct
13 Correct 257 ms 46392 KB Output is correct
14 Correct 336 ms 47216 KB Output is correct
15 Correct 462 ms 52404 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2620 ms 55464 KB Output is correct
2 Correct 2876 ms 55448 KB Output is correct
3 Correct 4467 ms 59596 KB Output is correct
4 Correct 382 ms 47536 KB Output is correct
5 Correct 263 ms 50740 KB Output is correct
6 Correct 900 ms 74420 KB Output is correct
7 Correct 2089 ms 62992 KB Output is correct
8 Correct 2924 ms 127112 KB Output is correct
9 Correct 3415 ms 68132 KB Output is correct
10 Runtime error 1469 ms 131072 KB Execution killed with signal 9
11 Correct 7626 ms 75124 KB Output is correct
12 Correct 2573 ms 73988 KB Output is correct
13 Correct 3134 ms 75560 KB Output is correct
14 Correct 4099 ms 98336 KB Output is correct
15 Correct 5585 ms 83352 KB Output is correct
16 Correct 5189 ms 94376 KB Output is correct
17 Correct 4971 ms 114236 KB Output is correct