oj.uz

Submission #472128

# Submission time Handle Problem Language Result Execution time Memory
472128 2021-09-13T06:31:36 Z jwvg0425 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 131076 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <fstream>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9+7)

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int h[200005];
int par[200005];
int in[200005];
int out[200005];
int byIn[200005];
vector<int> byOut[200005];
vector<int> edge[200005];
vector<int> byH[200005];
map<ii, int> ans;
int t = 1;

void dfs(int root)
{
    in[root] = t;
    byIn[t] = root;
    for (auto& e : edge[root])
    {
        t++;
        dfs(e);
    }
    out[root] = t;
    byOut[t].push_back(root);
}

int query(int r1, int r2)
{
    vector<ii> ts;
    for (auto& x : byH[r1])
    {
        ts.emplace_back(in[x], -1);
        ts.emplace_back(out[x], 1);
    }

    for (auto& x : byH[r2])
        ts.emplace_back(in[x], 0);

    sort(all(ts));

    int res = 0;
    int cnt = 0;
    for (auto& ti : ts)
    {
        if (ti.yy == 0)
            res += cnt;
        else
            cnt -= ti.yy;
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, r, q;
    cin >> n >> r >> q;

    cin >> h[1];
    byH[h[1]].push_back(1);

    for (int i = 2; i <= n; i++)
    {
        cin >> par[i] >> h[i];
        edge[par[i]].push_back(i);
        byH[h[i]].push_back(i);
    }

    dfs(1);
    
    for (int i = 1; i <= r; i++)
    {
        if (byH[i].size() < 450)
            continue;

        int cnt = 0;
        vector<int> psum(n + 5);

        for (int c = 1; c <= n; c++)
        {
            int x = byIn[c];

            if (h[x] == i)
            {
                psum[c]++;
                cnt++;
            }
            psum[c] += psum[c - 1];

            ans[{ i, h[x] }] += cnt;

            for (auto& o : byOut[c])
            {
                if (h[o] == i)
                    cnt--;
            }
        }

        for (int x = 1; x <= n; x++)
        {
            if (byH[h[x]].size() < 450)
                ans[{h[x], i}] += psum[out[x]] - psum[in[x]];
        }
    }

    for (int i = 0; i < q; i++)
    {
        int r1, r2;

        cin >> r1 >> r2;

        if (byH[r1].size() < 450 && byH[r2].size() < 450)
        {
            cout << query(r1, r2) << endl;
        }
        else
        {
            cout << ans[{ r1, r2 }] << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14408 KB Output is correct
2 Correct 10 ms 14408 KB Output is correct
3 Correct 13 ms 14376 KB Output is correct
4 Correct 14 ms 14408 KB Output is correct
5 Correct 18 ms 14408 KB Output is correct
6 Correct 33 ms 14408 KB Output is correct
7 Correct 47 ms 14408 KB Output is correct
8 Correct 39 ms 14536 KB Output is correct
9 Correct 77 ms 15040 KB Output is correct
10 Correct 125 ms 14920 KB Output is correct
11 Correct 222 ms 15304 KB Output is correct
12 Correct 215 ms 15816 KB Output is correct
13 Correct 288 ms 15816 KB Output is correct
14 Correct 563 ms 16200 KB Output is correct
15 Correct 551 ms 18888 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2198 ms 20280 KB Output is correct
2 Correct 2456 ms 19784 KB Output is correct
3 Correct 4700 ms 22100 KB Output is correct
4 Correct 463 ms 16316 KB Output is correct
5 Correct 525 ms 17928 KB Output is correct
6 Correct 1685 ms 63772 KB Output is correct
7 Correct 3379 ms 36668 KB Output is correct
8 Runtime error 3122 ms 131076 KB Execution killed with signal 9
9 Correct 5013 ms 24820 KB Output is correct
10 Runtime error 2615 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8023 ms 26728 KB Time limit exceeded
12 Correct 2347 ms 30660 KB Output is correct
13 Correct 3051 ms 31176 KB Output is correct
14 Correct 5307 ms 74768 KB Output is correct
15 Correct 5967 ms 37396 KB Output is correct
16 Correct 5610 ms 42660 KB Output is correct
17 Correct 6941 ms 85384 KB Output is correct