oj.uz

Submission #492264

# Submission time Handle Problem Language Result Execution time Memory
492264 2021-12-06T10:18:04 Z lukameladze Regions (IOI09_regions) C++14
100 / 100
 6741 ms 67172 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 = 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],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 13 ms 28488 KB Output is correct
2 Correct 13 ms 28436 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Correct 20 ms 28436 KB Output is correct
5 Correct 22 ms 28444 KB Output is correct
6 Correct 35 ms 28544 KB Output is correct
7 Correct 43 ms 28616 KB Output is correct
8 Correct 47 ms 28652 KB Output is correct
9 Correct 38 ms 29432 KB Output is correct
10 Correct 104 ms 29512 KB Output is correct
11 Correct 140 ms 30152 KB Output is correct
12 Correct 119 ms 30972 KB Output is correct
13 Correct 223 ms 31060 KB Output is correct
14 Correct 400 ms 31816 KB Output is correct
15 Correct 369 ms 35892 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2305 ms 37696 KB Output is correct
2 Correct 2824 ms 37348 KB Output is correct
3 Correct 3806 ms 40812 KB Output is correct
4 Correct 258 ms 31980 KB Output is correct
5 Correct 439 ms 34488 KB Output is correct
6 Correct 665 ms 38248 KB Output is correct
7 Correct 1741 ms 38008 KB Output is correct
8 Correct 1108 ms 53204 KB Output is correct
9 Correct 2893 ms 46540 KB Output is correct
10 Correct 4875 ms 65636 KB Output is correct
11 Correct 6741 ms 51144 KB Output is correct
12 Correct 2161 ms 49708 KB Output is correct
13 Correct 2597 ms 51120 KB Output is correct
14 Correct 2944 ms 54720 KB Output is correct
15 Correct 4587 ms 56500 KB Output is correct
16 Correct 4396 ms 65764 KB Output is correct
17 Correct 4054 ms 67172 KB Output is correct