Submission #843887

#	Time	Username	Problem	Language	Result	Execution time	Memory
843887		mickey080929	Telegraph (JOI16_telegraph)	C++14	100 / 100	44 ms	12116 KiB

telegraph

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<long long, long long> pll;

const ll inf = 2e18;

ll n;
pll adj[100010];
vector<pll> rev[100010];
ll cycle[100010];
ll vis[100010];
ll con[100010];
ll mn[100010];
ll id = 0;

ll find_cycle(ll x, ll num) {
    vis[x] = num;
    auto &[y, c] = adj[x];
    if (vis[y] == num) {
        cycle[x] = ++id;
        return y;
    }
    if (vis[y]) return -1;
    ll ret = find_cycle(y, num);
    if (ret == -1) return -1;
    cycle[x] = id;
    if (x == ret) return -1;
    return ret;
}

int main() {
    scanf("%lld", &n);
    ll tot = 0;
    for (ll i=1; i<=n; i++) {
        ll j, c;
        scanf("%lld %lld", &j, &c);
        adj[i] = make_pair(j, c);
        rev[j].emplace_back(i, c);
        tot += c;
    }
    ll num = 0;
    for (ll i=1; i<=n; i++) {
        if (!vis[i]) {
            find_cycle(i, ++num);
        }
    }
    bool flag = false;
    for (ll i=2; i<=n; i++) {
        if (cycle[i] != cycle[1]) {
            flag = true;
            break;
        }
    }
    if (!flag) {
        printf("0");
        return 0;
    }
    for (ll i=1; i<=id; i++) {
        mn[i] = inf;
    }
    ll ans = 0;
    for (ll i=1; i<=n; i++) {
        if (rev[i].empty()) continue;
        sort(rev[i].begin(), rev[i].end(), [&] (pll &u, pll &v) { return u.second > v.second; });
        ans += rev[i][0].second;
        if (!cycle[rev[i][0].first]) {
            con[cycle[i]] = 1;
        }
        mn[cycle[i]] = min(mn[cycle[i]], rev[i][0].second - (rev[i].size() == 1 ? 0 : rev[i][1].second));
    }
    for (ll i=1; i<=id; i++) {
        if (!con[i]) {
            ans -= mn[i];
        }
    }
    printf("%lld", tot - ans);
}

Compilation message (stderr)

telegraph.cpp: In function 'll find_cycle(ll, ll)':
telegraph.cpp:20:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     auto &[y, c] = adj[x];
      |           ^
telegraph.cpp: In function 'int main()':
telegraph.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%lld", &n);
      |     ~~~~~^~~~~~~~~~~~
telegraph.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%lld %lld", &j, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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