oj.uz

Submission #1086745

# Submission time Handle Problem Language Result Execution time Memory
1086745 2024-09-11T11:51:57 Z moonpay Regions (IOI09_regions) C++17
0 / 100
 8000 ms 41280 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;
        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 3 ms 7512 KB Output isn't correct
2 Incorrect 3 ms 7512 KB Output isn't correct
3 Incorrect 4 ms 7512 KB Output isn't correct
4 Incorrect 5 ms 7548 KB Output isn't correct
5 Incorrect 7 ms 7568 KB Output isn't correct
6 Incorrect 12 ms 7512 KB Output isn't correct
7 Incorrect 16 ms 7512 KB Output isn't correct
8 Incorrect 14 ms 7512 KB Output isn't correct
9 Incorrect 27 ms 7768 KB Output isn't correct
10 Incorrect 47 ms 7984 KB Output isn't correct
11 Incorrect 69 ms 8272 KB Output isn't correct
12 Incorrect 91 ms 8636 KB Output isn't correct
13 Incorrect 111 ms 8356 KB Output isn't correct
14 Incorrect 187 ms 9040 KB Output isn't correct
15 Incorrect 176 ms 10708 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 11224 KB Time limit exceeded
2 Execution timed out 8096 ms 10356 KB Time limit exceeded
3 Execution timed out 8087 ms 12496 KB Time limit exceeded
4 Runtime error 18 ms 16984 KB Execution killed with signal 11
5 Runtime error 16 ms 19536 KB Execution killed with signal 11
6 Runtime error 17 ms 18644 KB Execution killed with signal 11
7 Runtime error 22 ms 19668 KB Execution killed with signal 11
8 Runtime error 30 ms 26596 KB Execution killed with signal 6
9 Runtime error 41 ms 26204 KB Execution killed with signal 11
10 Runtime error 57 ms 32708 KB Execution killed with signal 11
11 Runtime error 48 ms 24004 KB Execution killed with signal 11
12 Runtime error 55 ms 28716 KB Execution killed with signal 6
13 Runtime error 49 ms 28612 KB Execution killed with signal 6
14 Runtime error 50 ms 27592 KB Execution killed with signal 11
15 Runtime error 49 ms 33728 KB Execution killed with signal 6
16 Runtime error 71 ms 41280 KB Execution killed with signal 11
17 Runtime error 50 ms 39844 KB Execution killed with signal 11