Submission #698354

#	Time	Username	Problem	Language	Result	Execution time	Memory
698354		pls33	Regions (IOI09_regions)	C++17	14 / 100	8087 ms	131072 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>;

void mark_heavy(int v, int p, map_t &heavy, vi32 &region, vvi32 &adj)
{
    heavy[region[v]]++;
    for (auto &next : adj[v])
    {
        if (next == p)
        {
            continue;
        }

        mark_heavy(next, v, heavy, region, adj);
    }
}

int mark_light(int v, int p, int need, vi32 &region, vvi32 &adj)
{
    int count = region[v] == need;

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

        count += mark_light(next, v, need, region, adj);
    }

    return count;
}

void find_hl(int v, int p, int bound,
             vi32 &size, vector<map_t> &heavy, vvp32 &light,
             vi32 &region, vvi32 &adj)
{
    for (auto &next : adj[v])
    {
        if (next == p)
        {
            continue;
        }

        find_hl(next, v, bound, size, heavy, light, region, adj);
        size[v] += size[next];
    }

    if (size[v] < bound)
    {
        light[region[v]].emplace_back(v, p);
        return;
    }

    mark_heavy(v, p, heavy[region[v]], region, adj);
}

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);
    }

    vi32 size(n, 1);
    vector<map_t> heavy(r);
    vvp32 light(r);
    int bound = (int)sqrt(n);

    find_hl(0, -1, bound, size, heavy, light, region, adj);

    // 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--;

        int count = 0;
        auto it = heavy[a].find(b);
        if (it != heavy[a].end())
        {
            count += it->second;
        }

        for (auto &[v, p] : light[a])
        {
            count += mark_light(v, p, b, region, adj);
        }

        cout << count << 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: 14 / 15
• Subtask 2: 0 / 85