oj.uz

Submission #1086743

# Submission time Handle Problem Language Result Execution time Memory
1086743 2024-09-11T11:45:27 Z moonpay Regions (IOI09_regions) C++17
0 / 100
 88 ms 41412 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
#include <iomanip>
#include <map>
#include <unordered_map>
using namespace std;

const int N = 200200;
const int R = 505;
vector<int> g[N];
vector<vector<int>> rr(R);
vector<int> region(N);


int timer = 1;
vector<int> lq(N), rq(N);

vector<int> vals = {0};
void dfs(int a) {
    lq[a] = timer;
    vals.push_back(region[a]);
    for (auto &d: g[a]) {
        timer++;
        dfs(d);
    }
    rq[a] = timer;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, q;
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        if (i == 1) {
            int x;
            cin >> x;
            region[i] = x;
        }
        else {
            int f, x;
            cin >> f >> x;
            region[i] = x;
            g[f].push_back(i);
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        rr[region[vals[i]]].push_back(i);
    }
    vector<vector<int>> zz(r + 1);
    for (int i = 1; i <= n; i++) zz[region[i]].push_back(i);
    assert(vals.size() == n + 1);
    for (int i = 0; i < q; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        assert(r1 <= R);
        int ans = 0;
        for (auto &vrt: zz[r1]) {
            int _l = lq[vrt], _r = rq[vrt];
            //cout << vrt << "  " << _l << " " << _r << "\n";
            ans += (upper_bound(rr[r2].begin(), rr[r2].end(), _r) - lower_bound(rr[r2].begin(), rr[r2].end(), _l));
        }
        cout << ans << "\n";
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from regions.cpp:5:
regions.cpp: In function 'int main()':
regions.cpp:56:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     assert(vals.size() == n + 1);
      |            ~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 7512 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 7512 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 7512 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 7512 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 7512 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 7512 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 7512 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 7512 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 7768 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 7768 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 8024 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 8536 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 8280 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 8792 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 10708 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 15 ms 11224 KB Time limit exceeded (wall clock)
2 Execution timed out 15 ms 10200 KB Time limit exceeded (wall clock)
3 Execution timed out 16 ms 12496 KB Time limit exceeded (wall clock)
4 Runtime error 16 ms 16984 KB Execution killed with signal 11
5 Runtime error 24 ms 19416 KB Execution killed with signal 11
6 Runtime error 21 ms 18756 KB Execution killed with signal 11
7 Runtime error 32 ms 19556 KB Execution killed with signal 11
8 Runtime error 48 ms 26572 KB Execution killed with signal 6
9 Runtime error 48 ms 26352 KB Execution killed with signal 11
10 Runtime error 53 ms 32708 KB Execution killed with signal 11
11 Runtime error 45 ms 24000 KB Execution killed with signal 11
12 Runtime error 60 ms 28588 KB Execution killed with signal 6
13 Runtime error 47 ms 28612 KB Execution killed with signal 6
14 Runtime error 88 ms 27644 KB Execution killed with signal 11
15 Runtime error 68 ms 33840 KB Execution killed with signal 6
16 Runtime error 79 ms 41412 KB Execution killed with signal 11
17 Runtime error 49 ms 39856 KB Execution killed with signal 11