제출 #472128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472128		jwvg0425	Regions (IOI09_regions)	C++17	85 / 100	8023 ms	131076 KiB

regions

#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 / 15
• Subtask 2: 70 / 85