oj.uz

Submission #928979

# Submission time Handle Problem Language Result Execution time Memory
928979 2024-02-17T11:28:00 Z boris_mihov Regions (IOI09_regions) C++17
100 / 100
 4264 ms 35168 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 5 ms 16984 KB Output is correct
4 Correct 6 ms 16828 KB Output is correct
5 Correct 7 ms 16984 KB Output is correct
6 Correct 11 ms 17236 KB Output is correct
7 Correct 17 ms 16984 KB Output is correct
8 Correct 31 ms 16984 KB Output is correct
9 Correct 26 ms 17496 KB Output is correct
10 Correct 51 ms 17752 KB Output is correct
11 Correct 77 ms 17884 KB Output is correct
12 Correct 77 ms 18520 KB Output is correct
13 Correct 112 ms 18416 KB Output is correct
14 Correct 127 ms 19008 KB Output is correct
15 Correct 147 ms 20936 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2522 ms 22144 KB Output is correct
2 Correct 4264 ms 21236 KB Output is correct
3 Correct 4022 ms 23764 KB Output is correct
4 Correct 154 ms 19012 KB Output is correct
5 Correct 222 ms 19968 KB Output is correct
6 Correct 473 ms 20116 KB Output is correct
7 Correct 632 ms 21588 KB Output is correct
8 Correct 647 ms 25416 KB Output is correct
9 Correct 1004 ms 27960 KB Output is correct
10 Correct 1581 ms 30652 KB Output is correct
11 Correct 1667 ms 27944 KB Output is correct
12 Correct 2320 ms 28968 KB Output is correct
13 Correct 2740 ms 28924 KB Output is correct
14 Correct 3169 ms 29168 KB Output is correct
15 Correct 3529 ms 32156 KB Output is correct
16 Correct 3722 ms 35168 KB Output is correct
17 Correct 3797 ms 35160 KB Output is correct