oj.uz

Submission #698422

# Submission time Handle Problem Language Result Execution time Memory
698422 2023-02-13T12:39:59 Z pls33 Regions (IOI09_regions) C++17
100 / 100
 4358 ms 66268 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

using map_t = map<int, int>;
using state_t = bitset<(size_t)25e3>;

void find_tour(int v, int p,
               int &index, vvi32 &occur, vp32 &tour,
               vi32 &region, vvi32 &adj)
{
    index++;
    occur[region[v]].push_back(index);
    tour.emplace_back(index, region[v]);

    for (auto &next : adj[v])
    {
        if (next == p)
        {
            continue;
        }

        find_tour(next, v, index, occur, tour, region, adj);
    }

    index++;
    occur[region[v]].push_back(-index);
}

void find_count(vi32 &occur, vp32 &tour, map_t &count)
{
    if (!occur.size())
    {
        return;
    }

    int balance = 0;
    size_t j = 0;
    p32 occur_start = {occur.front(), 0};

    for (size_t i = distance(tour.begin(), lower_bound(tour.begin(), tour.end(), occur_start));
         i < tour.size() && j < occur.size();
         i++)
    {
        while (j < occur.size() && abs(occur[j]) < tour[i].first)
        {
            balance += occur[j] > 0 ? 1 : -1;
            j++;
        }

        count[tour[i].second] += balance;
    }
}

int find_single(vi32 &occur, vi32 &occur_other)
{
    if (!occur.size())
    {
        return 0;
    }

    int balance = 0;
    int count = 0;
    size_t j = 0;

    for (size_t i = 0;
         i < occur_other.size() && j < occur.size();
         i++)
    {
        if (occur_other[i] < 0)
        {
            continue;
        }
        while (j < occur.size() && abs(occur[j]) < occur_other[i])
        {
            balance += occur[j] > 0 ? 1 : -1;
            j++;
        }

        count += balance;
    }

    return count;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("region.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
    freopen("con", "r", stdin);
    system("pause"); });
#endif
#endif

    int n, r, q;
    cin >> n >> r >> q;

    vi32 region(n);
    vvi32 adj(n);

    cin >> region[0];
    region[0]--;

    for (int i = 1; i < n; i++)
    {
        int parent;
        cin >> parent >> region[i];

        parent--;
        region[i]--;
        adj[i].push_back(parent);
        adj[parent].push_back(i);
    }

    vvi32 occur(r);
    vector<map_t> count(r);
    vp32 tour;

    // ???????????
    int index = 0;
    find_tour(0, -1, index, occur, tour, region, adj);

    size_t bound = size_t(sqrt(n) * 2.71828182845);
    state_t small;
    for (int i = 0; i < r; i++)
    {
        if (!occur[i].size())
        {
            continue;
        }

        if (occur[i].size() < bound)
        {
            small[i] = true;
            continue;
        }

        find_count(occur[i], tour, count[i]);
    }

    // galimai reikia rast tik tiem regionam, kur dydis > sqrt(n)????
    for (int i = 0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;

        a--;
        b--;

        if (small[a])
        {
            cout << find_single(occur[a], occur[b]) << endl;
            continue;
        }

        cout << count[a][b] << endl;
    }

    return 0;
}

Compilation message

regions.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
regions.cpp:31: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   31 | #pragma endregion
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 280 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 14 ms 464 KB Output is correct
7 Correct 23 ms 464 KB Output is correct
8 Correct 30 ms 464 KB Output is correct
9 Correct 35 ms 1488 KB Output is correct
10 Correct 69 ms 1232 KB Output is correct
11 Correct 104 ms 1616 KB Output is correct
12 Correct 107 ms 2640 KB Output is correct
13 Correct 124 ms 2256 KB Output is correct
14 Correct 177 ms 2764 KB Output is correct
15 Correct 205 ms 9816 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 8760 KB Output is correct
2 Correct 1978 ms 7112 KB Output is correct
3 Correct 1948 ms 12912 KB Output is correct
4 Correct 198 ms 3276 KB Output is correct
5 Correct 311 ms 7700 KB Output is correct
6 Correct 827 ms 23176 KB Output is correct
7 Correct 1303 ms 23752 KB Output is correct
8 Correct 1781 ms 66268 KB Output is correct
9 Correct 1539 ms 16788 KB Output is correct
10 Correct 1747 ms 29448 KB Output is correct
11 Correct 2045 ms 18860 KB Output is correct
12 Correct 2081 ms 18068 KB Output is correct
13 Correct 2770 ms 20620 KB Output is correct
14 Correct 4358 ms 33316 KB Output is correct
15 Correct 2901 ms 30804 KB Output is correct
16 Correct 2874 ms 49416 KB Output is correct
17 Correct 3099 ms 59656 KB Output is correct