oj.uz

Submission #881671

# Submission time Handle Problem Language Result Execution time Memory
881671 2023-12-01T17:53:09 Z sheldon Regions (IOI09_regions) C++14
55 / 100
 8000 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 = 1; i <= n; ++i) {
                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 3 ms 13412 KB Output is correct
3 Correct 3 ms 13400 KB Output is correct
4 Correct 4 ms 13400 KB Output is correct
5 Correct 7 ms 13400 KB Output is correct
6 Correct 13 ms 13400 KB Output is correct
7 Correct 20 ms 13632 KB Output is correct
8 Correct 25 ms 13652 KB Output is correct
9 Correct 45 ms 13912 KB Output is correct
10 Correct 93 ms 13912 KB Output is correct
11 Correct 166 ms 14168 KB Output is correct
12 Correct 193 ms 14424 KB Output is correct
13 Correct 316 ms 14424 KB Output is correct
14 Correct 410 ms 14960 KB Output is correct
15 Correct 579 ms 17148 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3158 ms 17656 KB Output is correct
2 Correct 3746 ms 17360 KB Output is correct
3 Correct 6731 ms 19160 KB Output is correct
4 Correct 597 ms 14952 KB Output is correct
5 Correct 814 ms 16152 KB Output is correct
6 Correct 1273 ms 32372 KB Output is correct
7 Correct 2968 ms 36676 KB Output is correct
8 Correct 3705 ms 60696 KB Output is correct
9 Execution timed out 8077 ms 21020 KB Time limit exceeded
10 Runtime error 407 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8092 ms 22584 KB Time limit exceeded
12 Execution timed out 8041 ms 23484 KB Time limit exceeded
13 Execution timed out 8002 ms 24424 KB Time limit exceeded
14 Execution timed out 8007 ms 38432 KB Time limit exceeded
15 Execution timed out 8093 ms 28480 KB Time limit exceeded
16 Execution timed out 8010 ms 33748 KB Time limit exceeded
17 Execution timed out 8057 ms 46756 KB Time limit exceeded