oj.uz

답안 #55862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55862 2018-07-09T06:17:50 Z 강태규(#1561) Telegraph (JOI16_telegraph) C++11
0 / 100
 4 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];
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%d", 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;
        int add = inf;
        for (int i = a[x], p = x; ; p = i, i = a[i]) {
            llong s = 0;
            int 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);
            if (i == x) break;
        }
        ans += sum + add;
    }
    
    printf("%lld\n", ans);
	return 0;
}

Compilation message

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%d", a + i, c + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -