oj.uz

Submission #896562

# Submission time Handle Problem Language Result Execution time Memory
896562 2024-01-01T16:49:51 Z danikoynov Worst Reporter 4 (JOI21_worst_reporter4) C++14
100 / 100
 904 ms 179096 KB 
/**
 ____ ____ ____ ____ ____ ____
||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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37212 KB Output is correct
2 Correct 9 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 19 ms 40016 KB Output is correct
6 Correct 17 ms 39260 KB Output is correct
7 Correct 16 ms 39000 KB Output is correct
8 Correct 18 ms 39812 KB Output is correct
9 Correct 16 ms 39512 KB Output is correct
10 Correct 16 ms 39064 KB Output is correct
11 Correct 14 ms 38856 KB Output is correct
12 Correct 20 ms 39288 KB Output is correct
13 Correct 15 ms 39256 KB Output is correct
14 Correct 18 ms 39000 KB Output is correct
15 Correct 16 ms 39004 KB Output is correct
16 Correct 19 ms 40264 KB Output is correct
17 Correct 16 ms 39260 KB Output is correct
18 Correct 14 ms 38748 KB Output is correct
19 Correct 16 ms 39292 KB Output is correct
20 Correct 16 ms 39076 KB Output is correct
21 Correct 15 ms 39004 KB Output is correct
22 Correct 17 ms 39416 KB Output is correct
23 Correct 17 ms 39000 KB Output is correct
24 Correct 17 ms 39260 KB Output is correct
25 Correct 16 ms 39084 KB Output is correct
26 Correct 15 ms 39260 KB Output is correct
27 Correct 16 ms 39516 KB Output is correct
28 Correct 16 ms 39404 KB Output is correct
29 Correct 18 ms 39548 KB Output is correct
30 Correct 18 ms 39688 KB Output is correct
31 Correct 16 ms 39516 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37212 KB Output is correct
2 Correct 9 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 19 ms 40016 KB Output is correct
6 Correct 17 ms 39260 KB Output is correct
7 Correct 16 ms 39000 KB Output is correct
8 Correct 18 ms 39812 KB Output is correct
9 Correct 16 ms 39512 KB Output is correct
10 Correct 16 ms 39064 KB Output is correct
11 Correct 14 ms 38856 KB Output is correct
12 Correct 20 ms 39288 KB Output is correct
13 Correct 15 ms 39256 KB Output is correct
14 Correct 18 ms 39000 KB Output is correct
15 Correct 16 ms 39004 KB Output is correct
16 Correct 19 ms 40264 KB Output is correct
17 Correct 16 ms 39260 KB Output is correct
18 Correct 14 ms 38748 KB Output is correct
19 Correct 16 ms 39292 KB Output is correct
20 Correct 16 ms 39076 KB Output is correct
21 Correct 15 ms 39004 KB Output is correct
22 Correct 17 ms 39416 KB Output is correct
23 Correct 17 ms 39000 KB Output is correct
24 Correct 17 ms 39260 KB Output is correct
25 Correct 16 ms 39084 KB Output is correct
26 Correct 15 ms 39260 KB Output is correct
27 Correct 16 ms 39516 KB Output is correct
28 Correct 16 ms 39404 KB Output is correct
29 Correct 18 ms 39548 KB Output is correct
30 Correct 18 ms 39688 KB Output is correct
31 Correct 16 ms 39516 KB Output is correct
32 Correct 18 ms 40028 KB Output is correct
33 Correct 704 ms 163440 KB Output is correct
34 Correct 532 ms 125932 KB Output is correct
35 Correct 686 ms 163436 KB Output is correct
36 Correct 517 ms 125604 KB Output is correct
37 Correct 458 ms 101800 KB Output is correct
38 Correct 399 ms 96676 KB Output is correct
39 Correct 501 ms 119824 KB Output is correct
40 Correct 393 ms 110844 KB Output is correct
41 Correct 352 ms 110776 KB Output is correct
42 Correct 455 ms 112020 KB Output is correct
43 Correct 372 ms 103076 KB Output is correct
44 Correct 627 ms 179096 KB Output is correct
45 Correct 455 ms 134276 KB Output is correct
46 Correct 287 ms 96696 KB Output is correct
47 Correct 514 ms 120532 KB Output is correct
48 Correct 400 ms 104520 KB Output is correct
49 Correct 294 ms 104372 KB Output is correct
50 Correct 518 ms 122492 KB Output is correct
51 Correct 317 ms 100984 KB Output is correct
52 Correct 591 ms 122396 KB Output is correct
53 Correct 341 ms 105904 KB Output is correct
54 Correct 364 ms 120000 KB Output is correct
55 Correct 490 ms 125196 KB Output is correct
56 Correct 465 ms 126620 KB Output is correct
57 Correct 447 ms 128464 KB Output is correct
58 Correct 471 ms 130508 KB Output is correct
59 Correct 534 ms 130880 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37212 KB Output is correct
2 Correct 9 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 19 ms 40016 KB Output is correct
6 Correct 17 ms 39260 KB Output is correct
7 Correct 16 ms 39000 KB Output is correct
8 Correct 18 ms 39812 KB Output is correct
9 Correct 16 ms 39512 KB Output is correct
10 Correct 16 ms 39064 KB Output is correct
11 Correct 14 ms 38856 KB Output is correct
12 Correct 20 ms 39288 KB Output is correct
13 Correct 15 ms 39256 KB Output is correct
14 Correct 18 ms 39000 KB Output is correct
15 Correct 16 ms 39004 KB Output is correct
16 Correct 19 ms 40264 KB Output is correct
17 Correct 16 ms 39260 KB Output is correct
18 Correct 14 ms 38748 KB Output is correct
19 Correct 16 ms 39292 KB Output is correct
20 Correct 16 ms 39076 KB Output is correct
21 Correct 15 ms 39004 KB Output is correct
22 Correct 17 ms 39416 KB Output is correct
23 Correct 17 ms 39000 KB Output is correct
24 Correct 17 ms 39260 KB Output is correct
25 Correct 16 ms 39084 KB Output is correct
26 Correct 15 ms 39260 KB Output is correct
27 Correct 16 ms 39516 KB Output is correct
28 Correct 16 ms 39404 KB Output is correct
29 Correct 18 ms 39548 KB Output is correct
30 Correct 18 ms 39688 KB Output is correct
31 Correct 16 ms 39516 KB Output is correct
32 Correct 18 ms 40028 KB Output is correct
33 Correct 704 ms 163440 KB Output is correct
34 Correct 532 ms 125932 KB Output is correct
35 Correct 686 ms 163436 KB Output is correct
36 Correct 517 ms 125604 KB Output is correct
37 Correct 458 ms 101800 KB Output is correct
38 Correct 399 ms 96676 KB Output is correct
39 Correct 501 ms 119824 KB Output is correct
40 Correct 393 ms 110844 KB Output is correct
41 Correct 352 ms 110776 KB Output is correct
42 Correct 455 ms 112020 KB Output is correct
43 Correct 372 ms 103076 KB Output is correct
44 Correct 627 ms 179096 KB Output is correct
45 Correct 455 ms 134276 KB Output is correct
46 Correct 287 ms 96696 KB Output is correct
47 Correct 514 ms 120532 KB Output is correct
48 Correct 400 ms 104520 KB Output is correct
49 Correct 294 ms 104372 KB Output is correct
50 Correct 518 ms 122492 KB Output is correct
51 Correct 317 ms 100984 KB Output is correct
52 Correct 591 ms 122396 KB Output is correct
53 Correct 341 ms 105904 KB Output is correct
54 Correct 364 ms 120000 KB Output is correct
55 Correct 490 ms 125196 KB Output is correct
56 Correct 465 ms 126620 KB Output is correct
57 Correct 447 ms 128464 KB Output is correct
58 Correct 471 ms 130508 KB Output is correct
59 Correct 534 ms 130880 KB Output is correct
60 Correct 8 ms 37208 KB Output is correct
61 Correct 8 ms 37324 KB Output is correct
62 Correct 8 ms 37332 KB Output is correct
63 Correct 7 ms 37464 KB Output is correct
64 Correct 720 ms 139304 KB Output is correct
65 Correct 537 ms 113528 KB Output is correct
66 Correct 654 ms 143812 KB Output is correct
67 Correct 517 ms 118376 KB Output is correct
68 Correct 446 ms 104784 KB Output is correct
69 Correct 435 ms 101512 KB Output is correct
70 Correct 755 ms 124104 KB Output is correct
71 Correct 688 ms 115676 KB Output is correct
72 Correct 790 ms 139156 KB Output is correct
73 Correct 763 ms 130616 KB Output is correct
74 Correct 885 ms 129704 KB Output is correct
75 Correct 741 ms 112876 KB Output is correct
76 Correct 694 ms 112756 KB Output is correct
77 Correct 904 ms 131260 KB Output is correct
78 Correct 656 ms 114216 KB Output is correct
79 Correct 786 ms 145848 KB Output is correct
80 Correct 607 ms 123592 KB Output is correct
81 Correct 563 ms 113052 KB Output is correct
82 Correct 776 ms 139704 KB Output is correct
83 Correct 318 ms 77764 KB Output is correct
84 Correct 751 ms 127876 KB Output is correct
85 Correct 768 ms 127940 KB Output is correct
86 Correct 732 ms 124944 KB Output is correct
87 Correct 728 ms 128216 KB Output is correct
88 Correct 732 ms 129064 KB Output is correct