oj.uz

Submission #881685

# Submission time Handle Problem Language Result Execution time Memory
881685 2023-12-01T18:03:19 Z sheldon Regions (IOI09_regions) C++14
95 / 100
 2829 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

int region[nax];
vector<int> edges[nax], positions[nax];
int tin[nax], tout[nax], who[nax];
int timer = 0;
unordered_map<int, int> mp[25005];

void dfs (int u, int p) {
    tin[u] = ++timer;
    who[timer] = u;
    positions[region[u]].push_back(timer);
    for (int v : edges[u]) {
        if (v != p) {
            dfs (v, u);
        }
    }
    tout[u] = timer;
}

void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[1];
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p >> region[i];
        edges[i].push_back(p);
        edges[p].push_back(i);
    }
    dfs (1, 0);
    const int B = sqrt(n) + 5;
    for (int reg = 1; reg <= r; ++reg) {
        if (positions[reg].size() >= B) {
            vector<int> pref(n + 2);
            for (int i = 1; i <= n; ++i) {
                if (region[who[i]] == reg) {
                    pref[i + 1]++;
                    pref[tout[who[i]] + 1]--;
                }
            }
            for (int i = 1; i <= n; ++i) {
                pref[i] += pref[i - 1];
                mp[reg][region[who[i]]] += pref[i];
            }
        }
    }
    while (q--) {
        int reg1, reg2;
        cin >> reg1 >> reg2;
        if (positions[reg1].size() >= B) {
            cout << mp[reg1][reg2] << endl;
        } else {
            int ans = 0;
            for (int i : positions[reg1]) {
                if (region[who[i]] == reg1) {
                    auto it1 = upper_bound(positions[reg2].begin(), positions[reg2].end(), tout[who[i]]) - positions[reg2].begin();
                    auto it2 = lower_bound(positions[reg2].begin(), positions[reg2].end(), i) - positions[reg2].begin();
                    if (it1 != 0) {
                        ans += (int) it1 - it2;
                    }
                }
            }
            cout << ans << endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:38:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   38 |         if (positions[reg].size() >= B) {
      |             ~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:55:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   55 |         if (positions[reg1].size() >= B) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13400 KB Output is correct
2 Correct 3 ms 13532 KB Output is correct
3 Correct 4 ms 13400 KB Output is correct
4 Correct 5 ms 13400 KB Output is correct
5 Correct 6 ms 13400 KB Output is correct
6 Correct 11 ms 13400 KB Output is correct
7 Correct 15 ms 13400 KB Output is correct
8 Correct 17 ms 13656 KB Output is correct
9 Correct 28 ms 13964 KB Output is correct
10 Correct 45 ms 13912 KB Output is correct
11 Correct 65 ms 14168 KB Output is correct
12 Correct 78 ms 14424 KB Output is correct
13 Correct 114 ms 14448 KB Output is correct
14 Correct 155 ms 14936 KB Output is correct
15 Correct 199 ms 17152 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 17704 KB Output is correct
2 Correct 1629 ms 17496 KB Output is correct
3 Correct 2129 ms 19216 KB Output is correct
4 Correct 166 ms 14936 KB Output is correct
5 Correct 241 ms 16216 KB Output is correct
6 Correct 369 ms 32400 KB Output is correct
7 Correct 836 ms 36608 KB Output is correct
8 Correct 857 ms 60568 KB Output is correct
9 Correct 1691 ms 20916 KB Output is correct
10 Runtime error 395 ms 131072 KB Execution killed with signal 9
11 Correct 2829 ms 22692 KB Output is correct
12 Correct 894 ms 23480 KB Output is correct
13 Correct 1283 ms 24272 KB Output is correct
14 Correct 1453 ms 38288 KB Output is correct
15 Correct 2249 ms 28412 KB Output is correct
16 Correct 2100 ms 33868 KB Output is correct
17 Correct 2123 ms 46520 KB Output is correct