oj.uz

Submission #1086746

# Submission time Handle Problem Language Result Execution time Memory
1086746 2024-09-11T11:53:00 Z moonpay Regions (IOI09_regions) C++17
0 / 100
 8000 ms 49092 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(26000);
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;
        cout.flush();
    }
}

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 8024 KB Output isn't correct
2 Incorrect 3 ms 8024 KB Output isn't correct
3 Incorrect 5 ms 8140 KB Output isn't correct
4 Incorrect 5 ms 8024 KB Output isn't correct
5 Incorrect 7 ms 8024 KB Output isn't correct
6 Incorrect 12 ms 8216 KB Output isn't correct
7 Incorrect 17 ms 8024 KB Output isn't correct
8 Incorrect 19 ms 8024 KB Output isn't correct
9 Incorrect 21 ms 8536 KB Output isn't correct
10 Incorrect 51 ms 8608 KB Output isn't correct
11 Incorrect 69 ms 8792 KB Output isn't correct
12 Incorrect 99 ms 9256 KB Output isn't correct
13 Incorrect 122 ms 9040 KB Output isn't correct
14 Incorrect 182 ms 9556 KB Output isn't correct
15 Incorrect 189 ms 11220 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8080 ms 11736 KB Time limit exceeded
2 Execution timed out 8044 ms 10968 KB Time limit exceeded
3 Execution timed out 8039 ms 13272 KB Time limit exceeded
4 Runtime error 25 ms 18980 KB Execution killed with signal 6
5 Runtime error 17 ms 21456 KB Execution killed with signal 6
6 Runtime error 20 ms 21208 KB Execution killed with signal 6
7 Runtime error 33 ms 23244 KB Execution killed with signal 6
8 Runtime error 32 ms 30668 KB Execution killed with signal 6
9 Runtime error 47 ms 32328 KB Execution killed with signal 6
10 Runtime error 46 ms 39884 KB Execution killed with signal 6
11 Runtime error 60 ms 32372 KB Execution killed with signal 6
12 Runtime error 86 ms 34804 KB Execution killed with signal 6
13 Runtime error 57 ms 34824 KB Execution killed with signal 6
14 Runtime error 60 ms 34772 KB Execution killed with signal 6
15 Runtime error 60 ms 41676 KB Execution killed with signal 6
16 Runtime error 88 ms 49092 KB Execution killed with signal 6
17 Runtime error 56 ms 46832 KB Execution killed with signal 6