oj.uz

Submission #698354

# Submission time Handle Problem Language Result Execution time Memory
698354 2023-02-13T09:25:05 Z pls33 Regions (IOI09_regions) C++17
14 / 100
 8000 ms 131072 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>;

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 8 ms 440 KB Output is correct
6 Correct 41 ms 2896 KB Output is correct
7 Correct 35 ms 976 KB Output is correct
8 Correct 53 ms 1716 KB Output is correct
9 Correct 726 ms 5480 KB Output is correct
10 Correct 197 ms 5544 KB Output is correct
11 Correct 620 ms 5028 KB Output is correct
12 Correct 2677 ms 11828 KB Output is correct
13 Correct 262 ms 3704 KB Output is correct
14 Correct 1098 ms 4580 KB Output is correct
15 Execution timed out 8021 ms 10640 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8010 ms 9128 KB Time limit exceeded
2 Execution timed out 8029 ms 8892 KB Time limit exceeded
3 Execution timed out 8087 ms 13724 KB Time limit exceeded
4 Runtime error 2602 ms 131072 KB Execution killed with signal 9
5 Runtime error 3748 ms 131072 KB Execution killed with signal 9
6 Runtime error 1628 ms 131072 KB Execution killed with signal 9
7 Runtime error 809 ms 131072 KB Execution killed with signal 9
8 Runtime error 2826 ms 131072 KB Execution killed with signal 9
9 Runtime error 1189 ms 131072 KB Execution killed with signal 9
10 Runtime error 2381 ms 131072 KB Execution killed with signal 9
11 Runtime error 1323 ms 131072 KB Execution killed with signal 9
12 Runtime error 1351 ms 131072 KB Execution killed with signal 9
13 Runtime error 1366 ms 131072 KB Execution killed with signal 9
14 Runtime error 1265 ms 131072 KB Execution killed with signal 9
15 Runtime error 981 ms 131072 KB Execution killed with signal 9
16 Runtime error 1073 ms 131072 KB Execution killed with signal 9
17 Runtime error 904 ms 131072 KB Execution killed with signal 9