oj.uz

Submission #1086748

# Submission time Handle Problem Language Result Execution time Memory
1086748 2024-09-11T11:56:10 Z moonpay Regions (IOI09_regions) C++17
15 / 100
 8000 ms 49484 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[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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 3 ms 8024 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 7 ms 8280 KB Output is correct
6 Correct 15 ms 8212 KB Output is correct
7 Correct 18 ms 8272 KB Output is correct
8 Correct 21 ms 8224 KB Output is correct
9 Correct 26 ms 8536 KB Output is correct
10 Correct 52 ms 8536 KB Output is correct
11 Correct 73 ms 8860 KB Output is correct
12 Correct 94 ms 9240 KB Output is correct
13 Correct 136 ms 8972 KB Output is correct
14 Correct 197 ms 9304 KB Output is correct
15 Correct 184 ms 11224 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8002 ms 11836 KB Time limit exceeded
2 Execution timed out 8098 ms 10968 KB Time limit exceeded
3 Execution timed out 8090 ms 13272 KB Time limit exceeded
4 Runtime error 20 ms 19032 KB Execution killed with signal 6
5 Runtime error 17 ms 21460 KB Execution killed with signal 6
6 Runtime error 21 ms 21200 KB Execution killed with signal 6
7 Runtime error 32 ms 23240 KB Execution killed with signal 6
8 Runtime error 35 ms 30920 KB Execution killed with signal 6
9 Runtime error 58 ms 32964 KB Execution killed with signal 6
10 Runtime error 49 ms 40832 KB Execution killed with signal 6
11 Runtime error 55 ms 32836 KB Execution killed with signal 6
12 Runtime error 65 ms 35268 KB Execution killed with signal 6
13 Runtime error 55 ms 35276 KB Execution killed with signal 6
14 Runtime error 78 ms 35384 KB Execution killed with signal 6
15 Runtime error 58 ms 42440 KB Execution killed with signal 6
16 Runtime error 64 ms 49484 KB Execution killed with signal 6
17 Runtime error 57 ms 47560 KB Execution killed with signal 6