oj.uz

Submission #1086750

# Submission time Handle Problem Language Result Execution time Memory
1086750 2024-09-11T12:00:20 Z moonpay Regions (IOI09_regions) C++17
40 / 100
 1911 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 = 26000;
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 3 ms 8024 KB Output is correct
3 Correct 4 ms 8024 KB Output is correct
4 Correct 7 ms 8024 KB Output is correct
5 Correct 10 ms 8280 KB Output is correct
6 Correct 14 ms 8472 KB Output is correct
7 Correct 16 ms 8280 KB Output is correct
8 Correct 21 ms 8276 KB Output is correct
9 Correct 47 ms 8792 KB Output is correct
10 Correct 149 ms 9316 KB Output is correct
11 Correct 177 ms 9048 KB Output is correct
12 Correct 375 ms 9856 KB Output is correct
13 Correct 365 ms 9304 KB Output is correct
14 Correct 323 ms 9560 KB Output is correct
15 Correct 280 ms 11572 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1180 ms 12060 KB Output is correct
2 Correct 1263 ms 10968 KB Output is correct
3 Correct 1803 ms 13772 KB Output is correct
4 Correct 1333 ms 72464 KB Output is correct
5 Correct 1911 ms 108920 KB Output is correct
6 Runtime error 73 ms 131072 KB Execution killed with signal 9
7 Runtime error 85 ms 131072 KB Execution killed with signal 9
8 Runtime error 80 ms 131072 KB Execution killed with signal 9
9 Runtime error 101 ms 131072 KB Execution killed with signal 9
10 Runtime error 89 ms 131072 KB Execution killed with signal 9
11 Runtime error 102 ms 131072 KB Execution killed with signal 9
12 Runtime error 104 ms 131072 KB Execution killed with signal 9
13 Runtime error 107 ms 131072 KB Execution killed with signal 9
14 Runtime error 96 ms 131072 KB Execution killed with signal 9
15 Runtime error 95 ms 131072 KB Execution killed with signal 9
16 Runtime error 94 ms 131072 KB Execution killed with signal 9
17 Runtime error 115 ms 131072 KB Execution killed with signal 9