Submission #1070095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070095		juicy	Telegraph (JOI16_telegraph)	C++17	0 / 100	1 ms	6748 KiB

telegraph

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n;
int nxt[N], c[N], root[N];
long long ma[N], sum[N], best[N], f[N];
bool vis[N];
vector<int> g[N];

void dfs(int u) {
    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
            ma[u] = max(ma[u], ma[v] + c[v]);
            f[u] += ma[v];
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> nxt[i] >> c[i];
        g[nxt[i]].push_back(i);
    }    
    for (int i = 1; i <= n; ++i) {
        if (!root[i]) {
            int j = i;
            vector<int> ver;
            for (; !vis[j]; j = nxt[j]) {
                vis[j] = 1;
                ver.push_back(j);
            }
            for (auto x : ver) {
                root[x] = j;
            }
            for (int k = i; k != j; k = nxt[k]) {
                vis[k] = 0;
            }
            for (auto x : ver) {
                if (vis[x]) {
                    dfs(x);
                    sum[j] += c[x] + f[x];
                }
            }
        }
    }
    if (count(vis + 1, vis + n + 1, 1) == n) {
        cout << 0;
        exit(0);
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) {
            ma[i] += sum[root[i]] - f[i];
            if (vis[nxt[i]]) {
                ma[nxt[i]] -= c[i];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        best[root[i]] = max(best[root[i]], ma[i]);
    }
    cout << accumulate(c + 1, c + n + 1, 0LL) - accumulate(best + 1, best + n + 1, 0LL); 
    return 0;
}

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