음악 추천 (백준 15957)

안녕하세요. 오늘은 음악을 추천할 거에요.

문제

https://www.acmicpc.net/problem/15957

아이디어

이 문제는 그냥 PBS + ETT로 풀면 됩니다.
1부터 K까지 모든 쿼리들을 순서대로 처리해준 다음 각 가수에 대해서 가능한지 여부를 확인해주면 됩니다. 이거는 브루트포스로 해도 됩니다. 단순하게 계산하면 TLE지만 전체 경우의 수로 따지면, 즉 가능한 경우의 수의 합이 N개이므로 결론적으로는 상관이 없습니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll tree[101010], N, K;
void change(ll idx, ll value)
{
    while (idx < N + 1) //idx가 딱 N이 될 수도 있음
    {
        tree[idx] += value;
        idx += idx & -idx;
    }
}
ll query(ll x)
{
    ll ans = 0;

    ll idx = x;
    while (idx > 0)
    {
        ans += tree[idx];
        idx -= idx & -idx;
    }

    return ans;
}

vector <ll> graph[101010];
ll in[101010] = { 0 }, out[101010] = { 0 }, num = 0;
void DFS(ll node)
{
    in[node] = ++num;
    for (ll next : graph[node])
        DFS(next);
    out[node] = num;
}

ll singer[101010] = { 0 }; //singer[x]: x번째 곡을 부른 가수의 번호
vector <ll> songs[101010]; //songs[x]: x번 가수가 부른 곡들 전부다
ll Left[101010] = { 0 }, Right[101010] = { 0 }; //PBS
vector <ll> mid[101010]; //PBS
ll Ans[101010] = { 0 }; //PBS에서의 Ans

void init()
{
    for (ll i = 0; i <= N + 1; i++) tree[i] = 0;
    for (ll i = 1; i <= K; i++) mid[i].clear();
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll J, a, b, c;
    vector <pair <pair <ll, ll>, ll> > qry;

    cin >> N >> K >> J;
    for (ll i = 2; i <= N; i++)
    {
        cin >> a;
        graph[a].push_back(i);
    }
    DFS(1);
    for (ll i = 1; i <= N; i++)
    {
        cin >> singer[i];
        songs[singer[i]].push_back(i);
    }

    for (ll i = 1; i <= N; i++) //i번째 가수
    {
        Left[i] = 1;
        Right[i] = K;
        Ans[i] = -1;
        if (songs[i].size() == 0) Right[i] = 1;
    }

    for (ll i = 0; i < K; i++)
    {
        cin >> a >> b >> c;
        qry.push_back({ {a,b},c });
    }
    sort(qry.begin(), qry.end());

    while (true)
    {
        init();

        ll done = true;
        for (ll i = 1; i <= N; i++)
        {
            if (Left[i] != Right[i])
            {
                done = false;
                mid[(Left[i] + Right[i]) / 2].push_back(i);
            }
        }
        if (done) break;

        for (ll i = 1; i <= K; i++)
        {
            ll diff = out[qry[i - 1].first.second] - in[qry[i - 1].first.second] + 1;
            change(in[qry[i - 1].first.second], qry[i - 1].second / diff);
            change(out[qry[i - 1].first.second] + 1, -qry[i - 1].second / diff);

            for (ll NowSinger : mid[i])
            {
                ll sum = 0, goal= J * songs[NowSinger].size();
                for (ll NowSong : songs[NowSinger])
                    sum += query(in[NowSong]);

                if (sum > goal) //평균이 J를 넘는다면
                {
                    Ans[NowSinger] = qry[i - 1].first.first;
                    Right[NowSinger] = i;
                }
                else Left[NowSinger] = i + 1;
            }
        }
    }

    for (ll i = 1; i <= N; i++)
        cout << Ans[singer[i]] << "\n";
}

감사합니다.