oj.uz

Submission #55853

# Submission time Handle Problem Language Result Execution time Memory
55853 2018-07-09T05:57:29 Z 강태규(#1561) Telegraph (JOI16_telegraph) C++11
0 / 100
 5 ms 2680 KB 
#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];
int c[100001];
vector<int> child[100001];
int visited[100001];
int finished[100001];

llong ans = 0;

pll dfs(int x, int p) {
    if (finished[x]) return pll(-1, -1);
    if (visited[x]) {
        finished[x] = 1;
        llong sum = 0;
        int mx = 0;
        for (int i : child[x]) {
            sum += c[i];
            if (i != p) mx = max(mx, c[i]);
        }
        return pll(sum - max(mx, c[p]), sum - mx);
    }
    else {
        visited[x] = 1;
        pll ret = dfs(a[x], x);
        if (finished[x]) {
            ans += ret.second;
            return ret;
        }
        finished[x] = 1;
        llong sum = 0;
        int mx = 0;
        for (int i : child[x]) {
            sum += c[i];
            if (i != p) mx = max(mx, c[i]);
        }
        ret.second = min(ret.second + sum - max(mx, c[p]), ret.first + sum - mx);
        ret.first += sum - mx;
        return ret;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", a + i, c + i);
        child[a[i]].push_back(i);
    }
    
    visited[1] = 1;
    int x = a[1], c = 1;
    while (!visited[x]) {
        ++c;
        visited[x] = 1;
        x = a[x];
    }
    if (x == 1 && c == 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, 0);
    }
    
    printf("%lld\n", ans);
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
telegraph.cpp:67: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -