Submission #698422

#	Time	Username	Problem	Language	Result	Execution time	Memory
698422		pls33	Regions (IOI09_regions)	C++17	100 / 100	4358 ms	66268 KiB

regions

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

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