Submission #928979

#	Time	Username	Problem	Language	Result	Execution time	Memory
928979		boris_mihov	Regions (IOI09_regions)	C++17	100 / 100	4264 ms	35168 KiB

regions

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, r, q;
int in[MAXN];
int out[MAXN];
int color[MAXN];
bool isOpen[MAXN];
std::vector <int> g[MAXN];
std::vector <std::pair <int,int>> byIn[MAXN];
std::vector <std::pair <int,int>> byInOut[MAXN];
int timer;

void dfs(int node)
{
    in[node] = ++timer;
    for (const int &u : g[node])
    {
        dfs(u);
    }

    out[node] = ++timer;
}

void solve()
{
    dfs(1);
    for (int i = 1 ; i <= n ; ++i)
    {
        byIn[color[i]].push_back({in[i], i});
        byInOut[color[i]].push_back({in[i], i});
        byInOut[color[i]].push_back({out[i], i});
    }

    for (int i = 1 ; i <= r ; ++i)
    {
        std::sort(byIn[i].begin(), byIn[i].end());
        std::sort(byInOut[i].begin(), byInOut[i].end());
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        int col1, col2;
        std::cin >> col1 >> col2;

        llong res = 0;
        int cntOpen = 0;
        int lPtr = 0, rPtr = 0;
        for (const auto &[time, u] : byInOut[col1])
        {
            isOpen[u] = false;
        }

        while (rPtr < byIn[col2].size())
        {
            if (lPtr == byInOut[col1].size() || byIn[col2][rPtr].first < byInOut[col1][lPtr].first)
            {
                res += cntOpen;
                rPtr++;
            } else
            {
                if (isOpen[byInOut[col1][lPtr].second])
                {
                    cntOpen--;
                } else
                {
                    cntOpen++;
                }

                isOpen[byInOut[col1][lPtr].second] ^= 1;
                lPtr++;
            }
        }

        std::cout << res << '\n' << std::flush;
    }
}

void input()
{
    std::cin >> n >> r >> q;
    std::cin >> color[1];

    for (int i = 2 ; i <= n ; ++i)
    {
        int par;
        std::cin >> par >> color[i];
        g[par].push_back(i);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    // fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while (rPtr < byIn[col2].size())
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if (lPtr == byInOut[col1].size() || byIn[col2][rPtr].first < byInOut[col1][lPtr].first)
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85