oj.uz

Submission #881669

# Submission time Handle Problem Language Result Execution time Memory
881669 2023-12-01T17:51:22 Z sheldon Regions (IOI09_regions) C++14
0 / 100
 724 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 {
            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) {
                        cout << 0 << endl;
                    } else {
                        cout << it1 - it2 << 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 13400 KB Time limit exceeded (wall clock)
2 Incorrect 3 ms 13400 KB Output isn't correct
3 Incorrect 3 ms 13400 KB Output isn't correct
4 Incorrect 5 ms 13400 KB Output isn't correct
5 Runtime error 4 ms 13596 KB Execution killed with signal 13
6 Runtime error 6 ms 13640 KB Execution killed with signal 13
7 Runtime error 6 ms 13640 KB Execution killed with signal 13
8 Runtime error 7 ms 13668 KB Execution killed with signal 13
9 Runtime error 10 ms 14044 KB Execution killed with signal 13
10 Runtime error 11 ms 13912 KB Execution killed with signal 13
11 Runtime error 14 ms 14256 KB Execution killed with signal 13
12 Execution timed out 32 ms 14620 KB Time limit exceeded (wall clock)
13 Execution timed out 37 ms 14636 KB Time limit exceeded (wall clock)
14 Execution timed out 35 ms 15020 KB Time limit exceeded (wall clock)
15 Execution timed out 27 ms 17184 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 56 ms 17940 KB Time limit exceeded (wall clock)
2 Execution timed out 54 ms 17456 KB Time limit exceeded (wall clock)
3 Execution timed out 48 ms 19388 KB Time limit exceeded (wall clock)
4 Execution timed out 34 ms 15008 KB Time limit exceeded (wall clock)
5 Execution timed out 60 ms 16356 KB Time limit exceeded (wall clock)
6 Execution timed out 724 ms 32568 KB Time limit exceeded (wall clock)
7 Execution timed out 125 ms 36752 KB Time limit exceeded (wall clock)
8 Execution timed out 240 ms 60744 KB Time limit exceeded (wall clock)
9 Execution timed out 121 ms 21428 KB Time limit exceeded (wall clock)
10 Runtime error 542 ms 131072 KB Execution killed with signal 9
11 Execution timed out 112 ms 22692 KB Time limit exceeded (wall clock)
12 Execution timed out 172 ms 23484 KB Time limit exceeded (wall clock)
13 Execution timed out 111 ms 24360 KB Time limit exceeded (wall clock)
14 Execution timed out 206 ms 38492 KB Time limit exceeded (wall clock)
15 Execution timed out 99 ms 28496 KB Time limit exceeded (wall clock)
16 Execution timed out 98 ms 33996 KB Time limit exceeded (wall clock)
17 Execution timed out 167 ms 46812 KB Time limit exceeded (wall clock)