제출 #1140253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140253		raphaelp	Regions (IOI09_regions)	C++20	100 / 100	4353 ms	75168 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))
class Fenwick
{
private:
    vector<int> ft;

public:
    Fenwick(int x) { ft.assign(x + 1, 0); }
    int PQ(int x)
    {
        x++;
        int sum = 0;
        for (; x < ft.size(); x += LSOne(x))
            sum += ft[x];
        return sum;
    }
    void update(int a, int b, int val)
    {
        for (; a; a -= LSOne(a))
            ft[a] -= val;
        for (; b; b -= LSOne(b))
            ft[b] += val;
    }
};
vector<int> dfs(int x, vector<vector<int>> &AR, vector<int> &deb, vector<int> &fin, int &cur, vector<vector<int>> &boss, vector<vector<int>> &empl, vector<int> &conv, vector<int> &current, vector<int> &reg)
{
    if (conv[reg[x]] != -1)
        current[conv[reg[x]]]++;
    for (int i = 0; i < boss.size(); i++)
    {
        if (i != conv[reg[x]])
            boss[i][reg[x]] += current[i];
    }
    deb[x] = cur++;
    vector<int> current2(boss.size());
    for (auto fils : AR[x])
    {
        vector<int> current3 = dfs(fils, AR, deb, fin, cur, boss, empl, conv, current, reg);
        for (int i = 0; i < boss.size(); i++)
        {
            current2[i] += current3[i];
        }
    }
    for (int i = 0; i < boss.size(); i++)
    {
        if (i != conv[reg[x]])
            empl[i][reg[x]] += current2[i];
    }
    if (conv[reg[x]] != -1)
    {
        current[conv[reg[x]]]--;
        current2[conv[reg[x]]]++;
    }
    fin[x] = cur;
    return current2;
}
int main()
{
    int N, R, Q;
    cin >> N >> R >> Q;
    vector<int> p(N), reg(N);
    vector<vector<int>> AR(N), Habs(R);
    for (int i = 0; i < N; i++)
    {
        if (i > 0)
        {
            cin >> p[i];
            p[i]--;
            AR[p[i]].push_back(i);
        }
        cin >> reg[i];
        reg[i]--;
        Habs[reg[i]].push_back(i);
    }
    Fenwick FT(N);
    vector<int> deb(N), fin(N), conv(R, -1);
    int bigs = 0;
    for (int i = 0; i < R; i++)
    {
        if (Habs[i].size() > 500)
        {
            conv[i] = bigs++;
        }
    }
    vector<vector<int>> boss(bigs, vector<int>(R)), empl(bigs, vector<int>(R));
    vector<int> current(bigs);
    int cur = 0;
    dfs(0, AR, deb, fin, cur, boss, empl, conv, current, reg);
    for (int i = 0; i < Q; i++)
    {
        int r1, r2;
        cin >> r1 >> r2;
        r1--, r2--;
        int ans = 0;
        if (conv[r1] != -1)
            ans = boss[conv[r1]][r2];
        else if (conv[r2] != -1)
            ans = empl[conv[r2]][r1];
        else
        {
            for (auto j : Habs[r1])
                FT.update(deb[j], fin[j], 1);
            for (auto j : Habs[r2])
                ans += FT.PQ(deb[j]);
            for (auto j : Habs[r1])
                FT.update(deb[j], fin[j], -1);
        }
        cout << ans << endl;
    }
}

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