oj.uz

Submission #1086749

# Submission time Handle Problem Language Result Execution time Memory
1086749 2024-09-11T11:59:00 Z moonpay Regions (IOI09_regions) C++17
40 / 100
 1856 ms 131072 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);
    vector<vector<int>> X(r + 1, vector<int> (r + 1));
    for (int r1 = 1; r1 <= r; r1++) {
        for (int r2 = 1; r2 <= r; r2++) {
            if (r1 == r2) continue;
            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));
            }
            X[r1][r2] = ans;
        }
    }
    assert(vals.size() == n + 1);
    for (int i = 0; i < q; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        cout << X[r1][r2] << 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:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     assert(vals.size() == n + 1);
      |            ~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8024 KB Output is correct
3 Correct 4 ms 8040 KB Output is correct
4 Correct 5 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct
6 Correct 14 ms 8280 KB Output is correct
7 Correct 26 ms 8292 KB Output is correct
8 Correct 21 ms 8280 KB Output is correct
9 Correct 46 ms 8792 KB Output is correct
10 Correct 137 ms 9308 KB Output is correct
11 Correct 175 ms 9296 KB Output is correct
12 Correct 398 ms 10044 KB Output is correct
13 Correct 360 ms 9304 KB Output is correct
14 Correct 314 ms 9672 KB Output is correct
15 Correct 310 ms 11724 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 11992 KB Output is correct
2 Correct 1274 ms 10968 KB Output is correct
3 Correct 1725 ms 13528 KB Output is correct
4 Correct 1320 ms 72460 KB Output is correct
5 Correct 1856 ms 108748 KB Output is correct
6 Runtime error 70 ms 131072 KB Execution killed with signal 9
7 Runtime error 77 ms 131072 KB Execution killed with signal 9
8 Runtime error 78 ms 131072 KB Execution killed with signal 9
9 Runtime error 91 ms 131072 KB Execution killed with signal 9
10 Runtime error 88 ms 131072 KB Execution killed with signal 9
11 Runtime error 97 ms 131072 KB Execution killed with signal 9
12 Runtime error 97 ms 131072 KB Execution killed with signal 9
13 Runtime error 98 ms 131072 KB Execution killed with signal 9
14 Runtime error 126 ms 131072 KB Execution killed with signal 9
15 Runtime error 93 ms 131072 KB Execution killed with signal 9
16 Runtime error 105 ms 131072 KB Execution killed with signal 9
17 Runtime error 112 ms 131072 KB Execution killed with signal 9