Submission #288133

#	Time	Username	Problem	Language	Result	Execution time	Memory
288133		Alexa2001	Telegraph (JOI16_telegraph)	C++17	100 / 100	70 ms	12536 KiB

telegraph

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
typedef long long ll;


int to[Nmax], cost[Nmax], mx1[Nmax], mx2[Nmax];
vector<int> v[Nmax];

ll ans = 0;
int used[Nmax];
int in_solve, in_cycle;

int n;

void upd(int &mx1, int &mx2, int cost)
{
    if(cost >= mx1) mx2 = mx1, mx1 = cost;
        else if(cost > mx2) mx2 = cost;
}

void mark(int node)
{
    used[node] = 2;

    for(auto it : v[node])
        if(used[it] != 2)
            mark(it);
}

int solve(int node)
{
    ++in_solve;

    while(!used[node])
    {
        used[node] = 1;
        node = to[node];
    }

    mark(node);

    int start = node;
    int ans = 2e9;

    do
    {
        if(mx1[to[node]] > cost[node])
            ans = 0;
        else ans = min(ans, mx1[to[node]] - mx2[to[node]]);

        node = to[node];

        ++in_cycle;
    }
    while(node != start);


    return ans;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n;

    int i;
    for(i=1; i<=n; ++i)
    {
        cin >> to[i] >> cost[i];
        v[to[i]].push_back(i);
    }

    for(i=1; i<=n; ++i)
        upd(mx1[to[i]], mx2[to[i]], cost[i]);

    for(i=1; i<=n; ++i)
        if(!used[i])
            ans += solve(i);

    for(i=1; i<=n; ++i) ans += cost[i] - mx1[i];

    if(in_cycle == n && in_solve == 1) ans = 0;

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30