Submission #896562

#	Time	Username	Problem	Language	Result	Execution time	Memory
896562		danikoynov	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	904 ms	179096 KiB

worst_reporter2

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 2e5 + 10;
const ll inf = 1e18;

int n, a[maxn], h[maxn];
ll c[maxn];
unordered_set < int > adj[maxn], g[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> h[i] >> c[i];
        if (a[i] != i)
            adj[a[i]].insert(i);
        if (a[i] != i)
            g[i].insert(a[i]);
    }
}

unordered_map < int, int > tag;

set < int > met;
vector < int > cycle;
int used[maxn], par[maxn];

void find_cycle(int v)
{
    used[v] = 1;
    for (int u : g[v])
    {
        if (used[u] == 2)
            continue;
        if (used[u] == 0)
        {
            par[u] = v;
            find_cycle(u);
        }
        else
        {
            int cur = v;
            while(cur != u)
            {
                ///cout << cur << " : " << u << endl;
                cycle.push_back(cur);
                met.insert(cur);
                cur = par[cur];
            }
            met.insert(cur);
            cycle.push_back(cur);
        }

    }
    used[v] = 2;
}

bool cmp(int v, int u)
{
    return h[v] > h[u];
}

void fix_graph()
{
    for (int i = 1; i <= n; i ++)
    {
        if (!used[i])
        {
            cycle.clear();
            met.clear();
            par[i] = -1;
            find_cycle(i);
            if (cycle.empty())
                continue;
            /**for (int v : cycle)
            cout << v << " ";
            cout << endl;
            cout << "-------------" << endl;*/
            vector < int > pivots;
            for (int ver : cycle)
            {
                vector < int > rem;
                for (int cur : adj[ver])

                {
                    if (met.find(cur) == met.end())
                    {
                        rem.push_back(cur);
                        ///adj[ver].erase(cur);
                        pivots.push_back(cur);
                    }
                }
                for (int cur : rem)
                    adj[ver].erase(cur);
            }
            for (int i = 0; i < cycle.size(); i ++)
            {
                int j = i + 1;
                j %= (int)(cycle.size());
                ///assert(adj[cycle[i]].find(cycle[j]) != adj[cycle[i]].end());
                adj[cycle[i]].erase(cycle[j]);
            }

            //for (int ver : pivots)
              //cout << "last " << ver << " " << cycle.back() << endl;
            sort(cycle.begin(), cycle.end(), cmp);
            for (int last : pivots)
                adj[cycle.back()].insert(last);
            for (int i = 1; i < cycle.size(); i ++)
            {
                adj[cycle[i - 1]].insert(cycle[i]);
                //cout << "edge " << cycle[i - 1] << " " << cycle[i] << endl;
            }
            /**cout << "--------" << endl;
            for (int cur : cycle)
                cout << cur << " " << h[cur] << endl;
            cout << endl;*/
        }
    }
}
void compress()
{
    vector < int > values;
    for (int i = 1; i <= n; i ++)
        values.push_back(h[i]);

    sort(values.begin(), values.end());

    for (int i = 0; i < n; i ++)
        tag[values[i]] = i + 1;

}

ll temp[maxn];

set < pair < int, ll > > spot[maxn];

void add_to_set(int v, pair < int, ll > cur)
{
    set < pair < int, ll > > :: iterator it = spot[v].lower_bound({cur.first, -inf});

    if (it != spot[v].end() && it -> first == cur.first)
    {
        cur.second += it -> second;

        spot[v].erase(it);
    }
    spot[v].insert(cur);
}

void dfs(int v)
{
    ///cout << "dfs " << v << endl;

    used[v] = 1;
    for (int u : adj[v])
    {
        ///cout << "nb " << v << " " << u << endl;
        dfs(u);

        if (spot[u].size() > spot[v].size())
            swap(spot[v], spot[u]);

        for (pair < int, ll > cur : spot[u])
            add_to_set(v, cur);

    }


    set < pair < int, ll > > :: iterator it;
    ll sum = 0;
    while(spot[v].size() > 0)
    {

        it = spot[v].lower_bound({tag[h[v]], inf});
        ///if (it != spot[v].end())

        if (it == spot[v].begin())
            break;
        it = prev(it);

        if (sum + it -> second > c[v])
        {
            pair < int, ll > nw = *it;
            nw.second -= (c[v] - sum);
            sum = c[v];
            spot[v].erase(it);
            add_to_set(v, nw);
            ///spot[v].insert(nw);
            break;
        }
        else
        {
            sum += it -> second;
            spot[v].erase(it);
        }

    }

    add_to_set(v, {1, sum});
    add_to_set(v, {tag[h[v]] + 1, c[v]});



}
int deg[maxn];
void calculate_states()
{
    for (int i = 1; i <= n; i ++)
        for (int u : adj[i])
            deg[u] ++;

    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (deg[i] != 0)
            continue;

        dfs(i);

        ll s = 0;
        for (pair < int, ll > cur : spot[i])
        {
            if (cur.first == 1)
                s += cur.second;
        }
        ans += s;
    }

    cout << ans << endl;
}
void solve()
{
    input();
    fix_graph();
    memset(used, 0, sizeof(used));
    compress();
    calculate_states();
}

int main()
{
    ///speed();
    ///freopen("test.txt", "r", stdin);
    solve();
    return 0;
}
/**
4
2 3 5
3 2 4
4 5 7
1 4 3
*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'void fix_graph()':
worst_reporter2.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int i = 0; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~
worst_reporter2.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |             for (int i = 1; i < cycle.size(); i ++)
      |                             ~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21