Submission #1086749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086749		moonpay	Regions (IOI09_regions)	C++17	40 / 100	1856 ms	131072 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 25 / 85