Submission #1191367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191367		Dedibeat	Jobs (BOI24_jobs)	C++20	0 / 100	140 ms	19600 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(T v)
{
    for(auto x : v)
        cout << x << " ";
    cout << "\n";
}
int w[300005];
int p[300005];
vector<int> adj[300005];
int main()
{
    ll n, s;
    cin >> n >> s;
    ll sum = 0, mx = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i] >> p[i];
        adj[p[i]].push_back(i);
        sum += w[i];
    }

 //   cout << sum << endl;
    using node = pair<int, int>;
    priority_queue<node, vector<node>, greater<>> q;
    vector<int> vis(n + 1, 0);
    for(int i = 1; i <= n; i++)
    {
        if(adj[i].size() == 0) 
        {
            q.emplace(w[i], i);
            vis[i] = 1;
        }
    }


    while(!q.empty())
    {
        mx = max(mx, sum);
        auto [cost, i] = q.top(); q.pop();
        if(vis[i]) continue;
        vis[i] = 1;
        sum -= cost;
      //  cout << cost << " " << i << endl;
        if(p[i] != 0)
        {
            q.emplace(w[p[i]], p[i]);
        }
    }

    cout << mx << "\n";
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31