oj.uz

Submission #543763

# Submission time Handle Problem Language Result Execution time Memory
543763 2022-03-31T10:35:44 Z Mazaalai Regions (IOI09_regions) C++17
1 / 100
 1793 ms 51852 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) {
    // if (regionCnt[a] >= k || regionCnt[b] >= k) {
    //     cout << a << " " << b << '\n';
    // }
    if (regionCnt[a] >= k) return dp1[compress[a]][b];
    if (regionCnt[b] >= k) return dp2[compress[b]][a];
    int ans = 0;
    {
        int x = 0, y = 0, cur = 0;
        while (x < out[a].size()-1 && y < out[b].size()-1) {
            if (out[a][x] < out[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:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (x < out[a].size()-1 && y < out[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~~
regions.cpp:64:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (x < out[a].size()-1 && y < out[b].size()-1) {
      |                                       ~~^~~~~~~~~~~~~~~~~
regions.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (x < in[a].size()-1 && y < in[b].size()-1) {
      |                ~~^~~~~~~~~~~~~~~~
regions.cpp:76:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (x < in[a].size()-1 && y < in[b].size()-1) {
      |                                      ~~^~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Incorrect 8 ms 14416 KB Output isn't correct
3 Incorrect 8 ms 14416 KB Output isn't correct
4 Incorrect 10 ms 14416 KB Output isn't correct
5 Incorrect 14 ms 14416 KB Output isn't correct
6 Incorrect 29 ms 14444 KB Output isn't correct
7 Incorrect 39 ms 14416 KB Output isn't correct
8 Incorrect 27 ms 14416 KB Output isn't correct
9 Incorrect 51 ms 14928 KB Output isn't correct
10 Incorrect 86 ms 14920 KB Output isn't correct
11 Incorrect 104 ms 15196 KB Output isn't correct
12 Incorrect 114 ms 15656 KB Output isn't correct
13 Incorrect 81 ms 15328 KB Output isn't correct
14 Incorrect 157 ms 16196 KB Output isn't correct
15 Incorrect 187 ms 19300 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 720 ms 19876 KB Output isn't correct
2 Incorrect 731 ms 18452 KB Output isn't correct
3 Incorrect 1069 ms 21908 KB Output isn't correct
4 Incorrect 230 ms 15948 KB Output isn't correct
5 Incorrect 349 ms 17992 KB Output isn't correct
6 Incorrect 593 ms 21600 KB Output isn't correct
7 Incorrect 631 ms 23320 KB Output isn't correct
8 Incorrect 909 ms 33844 KB Output isn't correct
9 Incorrect 1076 ms 23624 KB Output isn't correct
10 Incorrect 1711 ms 51852 KB Output isn't correct
11 Incorrect 1793 ms 23112 KB Output isn't correct
12 Incorrect 939 ms 26420 KB Output isn't correct
13 Incorrect 1193 ms 26784 KB Output isn't correct
14 Incorrect 1311 ms 30000 KB Output isn't correct
15 Incorrect 1466 ms 31940 KB Output isn't correct
16 Incorrect 1653 ms 39016 KB Output isn't correct
17 Incorrect 1618 ms 41128 KB Output isn't correct