oj.uz

Submission #944391

# Submission time Handle Problem Language Result Execution time Memory
944391 2024-03-12T16:35:11 Z FucKanh Regions (IOI09_regions) C++14
0 / 100
 1613 ms 38764 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

const int maxn = 2e5 + 2;
const int maxr = 25002;

int cnt[450][maxr], c[maxr], tin[maxn], tout[maxn], t, h[maxn], id[maxn], sz[maxr];
vector<int> a[maxn];
vector<pii> in[maxn];

void dfs(int u, int pa = -1) {
    tin[u] = ++t;
    if (!c[h[u]]) c[h[u]] = u;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (v == pa) continue;
        dfs(v, u);
    }
//    cerr << "out " << u << " " << h[u] << " : " << c[h[u]] << endl;
    tout[u] = t;
    in[h[u]].push_back({tin[u], tout[u]});
}

void dfsc(int u, int check, int pa = -1) {
    if (h[u] == check && c[check] == 0) c[check] = u;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (v == pa) continue;
        dfsc(v, check, u);
    }
    if (c[check] == u) c[check] = 0;
    if (c[check]) cnt[id[check]][h[u]]++;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n,r,q; cin >> n >> r >> q;
    cin >> h[1];
    for (int i = 2; i <= n; i++) {
        int x; cin >> x >> h[i];
        a[x].push_back(i);
        sz[h[i]]++;
    }
    for (int i = 1; i <= r; i++) {
        in[i].push_back({0,0});
    }
    dfs(1);

//    for (int i = 1; i <= r; i++) {
//        cerr << i << ": " << endl;
//        for (int j = 1; j < in[i].size(); j++) {
//            cerr << in[i][j] << " " << out[i][j] << endl;
//        }
//    }

    int dem = 0;
    for (int i = 1; i <= r; i++) {
        sort(in[i].begin() + 1, in[i].end());
        if (sz[i] >= 500) {
            id[i] = ++dem;
            c[i] = 0;
            dfsc(1, i);
//            cerr << i << ": " << endl;
//            for (int j = 1; j <= r; j++) {
//                cerr << cnt[dem][j] << " ";
//            } cerr << endl;
        }
    }

    cout << flush;
    for (int i =0; i < q; i++) {
        int r1, r2; cin >> r1 >> r2;
        if (sz[r1] >= 500) {
            cout << cnt[id[r1]][r2] << endl;
        }
        else {
            int pos = 1;
            int ans = 0;
//            cerr << r1 << ": ";
//            for (int i = 1; i < in[r1].size(); i++) {
//                cerr << in[r1][i].first <<  " " << in[r1][i].second << endl;
//            }
//            cerr << r2 << ": ";
//            for (int i = 1; i < in[r2].size(); i++) {
//                cerr << in[r2][i].first <<  " " << in[r2][i].second << endl;
//            }
            for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
                while (pos < in[r2].size() && in[r2][pos].first < in[r1][i].first) pos++;
                while (pos < in[r2].size() && in[r2][pos].first >= in[r1][i].first && in[r2][pos].second <= in[r1][i].second) ans++, pos++;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < a[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfsc(int, int, int)':
regions.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < a[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:90:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
regions.cpp:90:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
      |                                                  ~~~~^~~~~~~~~~~~~~~
regions.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 while (pos < in[r2].size() && in[r2][pos].first < in[r1][i].first) pos++;
      |                        ~~~~^~~~~~~~~~~~~~~
regions.cpp:92:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                 while (pos < in[r2].size() && in[r2][pos].first >= in[r1][i].first && in[r2][pos].second <= in[r1][i].second) ans++, pos++;
      |                        ~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10840 KB Output isn't correct
2 Incorrect 2 ms 10840 KB Output isn't correct
3 Incorrect 4 ms 10840 KB Output isn't correct
4 Incorrect 5 ms 10840 KB Output isn't correct
5 Incorrect 6 ms 10840 KB Output isn't correct
6 Incorrect 11 ms 10840 KB Output isn't correct
7 Incorrect 22 ms 10840 KB Output isn't correct
8 Incorrect 15 ms 10840 KB Output isn't correct
9 Incorrect 27 ms 11352 KB Output isn't correct
10 Incorrect 34 ms 11308 KB Output isn't correct
11 Incorrect 58 ms 11600 KB Output isn't correct
12 Incorrect 57 ms 12376 KB Output isn't correct
13 Incorrect 94 ms 11680 KB Output isn't correct
14 Incorrect 92 ms 12420 KB Output isn't correct
15 Incorrect 112 ms 16272 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 17280 KB Output isn't correct
2 Incorrect 618 ms 15620 KB Output isn't correct
3 Incorrect 965 ms 19532 KB Output isn't correct
4 Incorrect 149 ms 12584 KB Output isn't correct
5 Incorrect 223 ms 14716 KB Output isn't correct
6 Incorrect 345 ms 18088 KB Output isn't correct
7 Incorrect 508 ms 16020 KB Output isn't correct
8 Incorrect 536 ms 22980 KB Output isn't correct
9 Incorrect 766 ms 21276 KB Output isn't correct
10 Incorrect 985 ms 27836 KB Output isn't correct
11 Incorrect 1328 ms 20248 KB Output isn't correct
12 Incorrect 672 ms 21844 KB Output isn't correct
13 Incorrect 912 ms 22632 KB Output isn't correct
14 Incorrect 1251 ms 25232 KB Output isn't correct
15 Incorrect 1268 ms 27964 KB Output isn't correct
16 Incorrect 1613 ms 37212 KB Output isn't correct
17 Incorrect 1463 ms 38764 KB Output isn't correct