oj.uz

Submission #130795

# Submission time Handle Problem Language Result Execution time Memory
130795 2019-07-16T05:42:33 Z 송준혁(#3172) Harbingers (CEOI09_harbingers) C++14
20 / 100
 1000 ms 12096 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;

int N;
vector<pii> adj[101010];
int P[101010];
LL A[101010], B[101010], ans[101010], D[101010];

void dfs(int u, int p){
    ans[u] = 1234567890123456ll, P[u] = p;
    for (int a=p; a!=0; a=P[a]) ans[u] = min(ans[u], A[u]*(D[u]-D[a]) + B[u] + ans[a]);
    if (u == 1) ans[u] = 0;
    for (pii v : adj[u]){
        if (v.first == p) continue;
        D[v.first] = D[u] + v.second;
        dfs(v.first, u);
    }
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<N; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(pii(v, w));
        adj[v].push_back(pii(u, w));
    }
    for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
    dfs(1, 0);
    for (int i=2; i<=N; i++) printf("%lld ", ans[i]);
    return 0;
}

Compilation message

harbingers.cpp: In function 'int main()':
harbingers.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
harbingers.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:30:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 17 ms 3064 KB Output is correct
3 Execution timed out 1070 ms 6880 KB Time limit exceeded
4 Execution timed out 1078 ms 8564 KB Time limit exceeded
5 Execution timed out 1077 ms 10232 KB Time limit exceeded
6 Execution timed out 1080 ms 12096 KB Time limit exceeded
7 Execution timed out 1075 ms 9064 KB Time limit exceeded
8 Execution timed out 1059 ms 12016 KB Time limit exceeded
9 Execution timed out 1087 ms 11856 KB Time limit exceeded
10 Execution timed out 1063 ms 11568 KB Time limit exceeded