oj.uz

Submission #543770

# Submission time Handle Problem Language Result Execution time Memory
543770 2022-03-31T10:48:23 Z Mazaalai Regions (IOI09_regions) C++17
100 / 100
 2209 ms 51804 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second
#define pb push_back
#define LINE "------------------------\n"
using namespace std;
using PII = pair <int, int>;
const int N = 2e5 + 5;
const int M = 25e3+5;
const int K = 160;
int k;
int par[N], region[N], regionCnt[M], compress[N];
vector <int> paths[N], in[N], out[N];
int n, m, q, last = 1, Comp = 1;
PII range[N];
void dfs(int pos, int p = 1) {
    in[region[pos]].pb(last++);
    for (auto& el : paths[pos]) 
        dfs(el, pos);
    out[region[pos]].pb(last-1);
}
int dp1[K][N], dp2[K][N];
int up[N], down[N];
void calc1(int a) { // r1, r2 => a == r1;
    for (int i = 1; i <= n; i++) {
        down[i] = down[par[i]]+(region[i]==a);
        dp1[compress[a]][region[i]] += down[i];
    }
}
void calc2(int a) { // r1, r2 => a == r2;
    for (int i = n; i > 0; i--) {
        up[i] = (region[i] == a);
        for (auto& el : paths[i]) up[i] += up[el];
        dp2[compress[a]][region[i]] += up[i];
    }
}
void calc() {
    dfs(1);
    k = sqrt(n);
    for (int i = 1; i <= n; i++) regionCnt[region[i]]++;
    for (int i = 1; i <= m; i++) {
        if (regionCnt[i] >= k) {
            // cout << "HERE: " << i << ' ' << regionCnt[i] << " " << Comp << ' ' << k << "\n";
            compress[i] = Comp++;
            calc1(i);
            calc2(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        in[i].pb(n+5);
        out[i].pb(n+5);
    }
}
int answer(int a, int b) {
    // cout << a << ' ' << regionCnt
    if (regionCnt[a] >= k) return dp1[compress[a]][b];
    if (regionCnt[b] >= k) return dp2[compress[b]][a];
    // cout << "IN " << a << ": "; for (auto el : in[a]) cout << el << ' '; cout << '\n';
    // cout << "OUT " << a << ": "; for (auto el : out[a]) cout << el << ' '; cout << '\n';
    // cout << "IN " << b << ": "; for (auto el : in[b]) cout << el << ' '; cout << '\n';
    int ans = 0;
    {
        int x = 0, y = 0, cur = 0;
        while (x < out[a].size()-1 || y < in[b].size()-1) {
            if (out[a][x] < in[b][y]) {
                ans += cur;
                x++;
            } else {
                cur++;
                y++;
            }
        }

    }
    {
        int x = 0, y = 0, cur = 0;
        while (x < in[a].size()-1 || y < in[b].size()-1) {
            if (in[a][x] < in[b][y]) {
                ans -= cur;
                x++;
            } else {
                cur++;
                y++;
            }
        }

    }
    return ans;
}
signed main() {
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
    cin >> n >> m >> q;
    cin >> region[1];
    for (int i = 2; i <= n; i++) {
        cin >> par[i] >> region[i];
        paths[par[i]].pb(i);
    }
    calc();
    for (int i = 1; i <= q; i++) {
        int a, b; cin >> a >> b;
        cout << answer(a, b) << endl;
    }
}

Compilation message

regions.cpp: In function 'int answer(int, int)':
regions.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (x < out[a].size()-1 || y < in[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~~
regions.cpp:65:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (x < out[a].size()-1 || y < in[b].size()-1) {
      |                                       ~~^~~~~~~~~~~~~~~~
regions.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while (x < in[a].size()-1 || y < in[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~
regions.cpp:78:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while (x < in[a].size()-1 || y < in[b].size()-1) {
      |                                      ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14380 KB Output is correct
2 Correct 8 ms 14416 KB Output is correct
3 Correct 9 ms 14416 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Correct 13 ms 14372 KB Output is correct
6 Correct 25 ms 14416 KB Output is correct
7 Correct 34 ms 14416 KB Output is correct
8 Correct 36 ms 14544 KB Output is correct
9 Correct 49 ms 14936 KB Output is correct
10 Correct 83 ms 14928 KB Output is correct
11 Correct 68 ms 15144 KB Output is correct
12 Correct 101 ms 15616 KB Output is correct
13 Correct 150 ms 15256 KB Output is correct
14 Correct 119 ms 16200 KB Output is correct
15 Correct 209 ms 19272 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 19872 KB Output is correct
2 Correct 938 ms 18444 KB Output is correct
3 Correct 1085 ms 21904 KB Output is correct
4 Correct 195 ms 15944 KB Output is correct
5 Correct 280 ms 18000 KB Output is correct
6 Correct 487 ms 21620 KB Output is correct
7 Correct 513 ms 23504 KB Output is correct
8 Correct 772 ms 33864 KB Output is correct
9 Correct 1456 ms 23624 KB Output is correct
10 Correct 1244 ms 51804 KB Output is correct
11 Correct 2209 ms 23300 KB Output is correct
12 Correct 910 ms 26420 KB Output is correct
13 Correct 1111 ms 26812 KB Output is correct
14 Correct 1375 ms 30000 KB Output is correct
15 Correct 1609 ms 31948 KB Output is correct
16 Correct 1703 ms 39080 KB Output is correct
17 Correct 1950 ms 41056 KB Output is correct