Submission #1093824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093824		jonghak9028	Telegraph (JOI16_telegraph)	C++17	100 / 100	37 ms	18124 KiB

telegraph

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 17712                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: js9028 <boj.kr/u/js9028>                    +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/17712                          #+#        #+#      #+#    */
/*   Solved: 2024/09/28 00:01:54 by js9028        ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <tuple>
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
using namespace std;

typedef long long ll;
const long long INF = 1e18 + 5;

int n;
pair<int, ll> nxt[101010];
vector<pair<int, ll>> radj[101010];
pair<ll, ll> cost[101010];

vector<vector<int>> cyl;
bool iscycle[101010];

ll eval[101010];
int tn[101010];
int nt = 1;
vector<int> tmp;
int get_cycle(int cur)
{
    tn[cur] = nt;
    int nx = nxt[cur].first;
    if (tn[nx] == nt)
    {
        tmp.push_back(cur);
        iscycle[cur] = 1;
        eval[nx] = nxt[cur].second;
        return nx;
    }
    else if (tn[nx])
    {
        return 0;
    }
    int ret = get_cycle(nx);
    if (ret)
    {
        tmp.push_back(cur);
        iscycle[cur] = 1;
        eval[nx] = nxt[cur].second;
        if (ret == cur)
            ret = 0;
    }

    return ret;
}

ll esum[101010];
ll me[101010];
int main()
{
    fastio;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        nxt[i] = {a, b};
        radj[a].push_back({i, b});
        esum[a] += b;
        me[a] = max(me[a], (ll)b);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!tn[i])
        {
            tmp.clear();
            get_cycle(i);
            if (!tmp.empty())
                cyl.push_back(tmp);
            if (tmp.size() == n)
            {
                cout << 0;
                return 0;
            }
            nt++;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!iscycle[i])
        {
            ans += esum[i] - me[i];
        }
    }

    for (auto &v : cyl)
    {
        ll sum = 0;
        for (int i : v)
        {
            ll mx = 0;
            cost[i].first = esum[i] - me[i];
            for (auto nx : radj[i])
            {
                if (!iscycle[nx.first])
                    mx = max(mx, nx.second);
            }
            cost[i].second = esum[i] - mx;
            sum += cost[i].first;
        }
        ll t = INF;
        for (int i : v)
        {
            t = min(t, sum - cost[i].first + cost[i].second);
        }
        ans += t;
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:88:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |             if (tmp.size() == n)
      |                 ~~~~~~~~~~~^~~~

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