oj.uz

Submission #881674

# Submission time Handle Problem Language Result Execution time Memory
881674 2023-12-01T17:57:07 Z sheldon Regions (IOI09_regions) C++14
95 / 100
 2620 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);
    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 += 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 4 ms 13472 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 10 ms 13400 KB Output is correct
7 Correct 14 ms 13400 KB Output is correct
8 Correct 17 ms 13656 KB Output is correct
9 Correct 27 ms 13912 KB Output is correct
10 Correct 44 ms 13912 KB Output is correct
11 Correct 66 ms 14168 KB Output is correct
12 Correct 81 ms 14424 KB Output is correct
13 Correct 117 ms 14424 KB Output is correct
14 Correct 174 ms 14936 KB Output is correct
15 Correct 187 ms 17240 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 17648 KB Output is correct
2 Correct 1564 ms 17416 KB Output is correct
3 Correct 2177 ms 19300 KB Output is correct
4 Correct 178 ms 14936 KB Output is correct
5 Correct 233 ms 16216 KB Output is correct
6 Correct 397 ms 32284 KB Output is correct
7 Correct 873 ms 36648 KB Output is correct
8 Correct 851 ms 60568 KB Output is correct
9 Correct 1652 ms 21124 KB Output is correct
10 Runtime error 395 ms 131072 KB Execution killed with signal 9
11 Correct 2620 ms 22696 KB Output is correct
12 Correct 830 ms 23516 KB Output is correct
13 Correct 1247 ms 24208 KB Output is correct
14 Correct 1394 ms 38444 KB Output is correct
15 Correct 2225 ms 28252 KB Output is correct
16 Correct 2308 ms 33752 KB Output is correct
17 Correct 2162 ms 46660 KB Output is correct