Submission #134585

#	Time	Username	Problem	Language	Result	Execution time	Memory
134585		imeimi2000	Telegraph (JOI16_telegraph)	C++17	100 / 100	68 ms	11768 KiB

telegraph

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
const int inf = 1e9 + 7;
const llong linf = 1e16;
int n;
int a[100001];
llong c[100001];
vector<int> child[100001];
int visited[100001];
int finished[100001];
vector<int> cyc;
 
void dfs(int x) {
    if (finished[x]) return;
    if (visited[x]) cyc.push_back(x);
    else {
        visited[x] = 1;
        dfs(a[x]);
        finished[x] = 1;
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%lld", a + i, c + i);
        child[a[i]].push_back(i);
    }
    
    visited[1] = 1;
    int x = a[1], cnt = 1;
    while (!visited[x]) {
        ++cnt;
        visited[x] = 1;
        x = a[x];
    }
    if (x == 1 && cnt == n) {
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        visited[i] = 0;
    }
    
    for (int i = 1; i <= n; ++i) {
        dfs(i);
    }
    
    llong ans = 0;
    for (int x : cyc) {
        llong sum = 0, add = linf;
        for (int i = a[x], p = x; ; p = i, i = a[i]) {
            llong s = 0, m = 0;
            for (int j : child[i]) {
                s += c[j];
                if (j != p) m = max(m, c[j]);
            }
            sum += s - max(m, c[p]);
            add = min(add, max(m, c[p]) - m);
            visited[i] = 0;
            if (i == x) break;
        }
        ans += sum + add;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (visited[i]) {
            llong sum = 0;
            llong mx = 0;
            for (int j : child[i]) {
                sum += c[j];
                mx = max(mx, c[j]);
            }
            ans += sum - mx;
        }
    }
    
    printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
telegraph.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%lld", a + i, c + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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