Submission #59081

#	Time	Username	Problem	Language	Result	Execution time	Memory
59081		choikiwon	Telegraph (JOI16_telegraph)	C++17	100 / 100	154 ms	64268 KiB

telegraph

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int N;
int A[MN], C[MN], vis[MN], del[MN];
vector<int> adj[MN], cycle;

ll dfs(int u, int t) {
    vis[u] = 1;
    ll ret = 0;
    ll sum = 0;
    int mx = 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(del[v]) continue;
        ret += dfs(v, 1);
        sum += C[v];
        mx = max(mx, C[v]);
    }
    if(t) sum -= mx;
    return ret += sum;
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &A[i], &C[i]);
        A[i]--;
        adj[ A[i] ].push_back(i);
    }

    ll ans = 0;
    for(int i = 0; i < N; i++) {
        if(vis[i]) continue;
        int u = i;
        while(!vis[u]) {
            vis[u] = 1;
            u = A[u];
        }

        cycle.clear();
        int t = u;
        while(1) {
            cycle.push_back(t);
            del[t] = 1;
            t = A[t];
            if(t == u) break;
        }

        int n = cycle.size();
        if(n == N) {
            printf("0");
            return 0;
        }
        ll sum = 0;
        vector<ll> V;
        for(int j = 0; j < n; j++) {
            int u = cycle[j];
            int v = cycle[ (j + n - 1) % n ];
            ll t1 = dfs(u, 1) + C[v];
            ll t2 = dfs(u, 0);
            sum += t2;
            V.push_back(t1 - t2);
        }
        sort(V.begin(), V.end());

        sum += V[0];
        for(int j = 1; j < n; j++) {
            if(V[j] >= 0) break;
            sum += V[j];
        }
        ans += sum;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

telegraph.cpp: In function 'll dfs(int, int)':
telegraph.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
telegraph.cpp: In function 'int main()':
telegraph.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
telegraph.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &A[i], &C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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