oj.uz

Submission #1086744

# Submission time Handle Problem Language Result Execution time Memory
1086744 2024-09-11T11:49:12 Z moonpay Regions (IOI09_regions) C++17
0 / 100
 8000 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 << endl;
    }
}

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 Incorrect 4 ms 7512 KB Output isn't correct
2 Incorrect 4 ms 7512 KB Output isn't correct
3 Incorrect 5 ms 7512 KB Output isn't correct
4 Incorrect 5 ms 7360 KB Output isn't correct
5 Incorrect 7 ms 7512 KB Output isn't correct
6 Incorrect 12 ms 7768 KB Output isn't correct
7 Incorrect 17 ms 7656 KB Output isn't correct
8 Incorrect 21 ms 7512 KB Output isn't correct
9 Incorrect 27 ms 7768 KB Output isn't correct
10 Incorrect 44 ms 7980 KB Output isn't correct
11 Incorrect 68 ms 8272 KB Output isn't correct
12 Incorrect 82 ms 8632 KB Output isn't correct
13 Incorrect 117 ms 8352 KB Output isn't correct
14 Incorrect 190 ms 8888 KB Output isn't correct
15 Incorrect 182 ms 10708 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8084 ms 11224 KB Time limit exceeded
2 Execution timed out 8071 ms 10200 KB Time limit exceeded
3 Execution timed out 8064 ms 12496 KB Time limit exceeded
4 Runtime error 13 ms 16984 KB Execution killed with signal 11
5 Runtime error 15 ms 19436 KB Execution killed with signal 11
6 Runtime error 21 ms 18640 KB Execution killed with signal 11
7 Runtime error 20 ms 19732 KB Execution killed with signal 11
8 Runtime error 29 ms 26572 KB Execution killed with signal 6
9 Runtime error 35 ms 26316 KB Execution killed with signal 11
10 Runtime error 40 ms 32716 KB Execution killed with signal 11
11 Runtime error 70 ms 24000 KB Execution killed with signal 11
12 Runtime error 79 ms 28612 KB Execution killed with signal 6
13 Runtime error 51 ms 28608 KB Execution killed with signal 6
14 Runtime error 69 ms 27592 KB Execution killed with signal 11
15 Runtime error 53 ms 33732 KB Execution killed with signal 6
16 Runtime error 73 ms 41412 KB Execution killed with signal 11
17 Runtime error 71 ms 39796 KB Execution killed with signal 11