| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130770 |
2019-07-16T04:52:54 Z |
이온조(#3169) |
Harbingers (CEOI09_harbingers) |
C++14 |
|
160 ms |
41880 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct line {
int A;
long long B;
long long get(int x) { return 1LL*A*x + B; }
};
struct node {
int lc, rc;
line l;
};
const int iNF = 1e9;
const long long INF = 5LL * 1e18;
node EMP = {-1, -1, {0, INF}};
node T[500009]; int to;
int root[100009];
void add(node pi, node &ni, int s, int e, line L) {
// printf("add: (%d, %d)\n", L.A, L.B);
ni = pi;
if(L.get(s) >= ni.l.get(s) && L.get(e) >= ni.l.get(e)) return;
if(L.get(s) <= ni.l.get(s) && L.get(e) <= ni.l.get(e)) {ni.l = L; return;}
int m = s+e >> 1;
if(L.get(s) > ni.l.get(s)) swap(L, ni.l);
if(L.get(m) < ni.l.get(m)) {
swap(L, ni.l);
ni.rc = to; T[to++] = EMP;
if(pi.rc == -1) add(EMP, T[ni.rc], m, e, L);
else add(T[pi.rc], T[ni.rc], m, e, L);
}
else {
ni.lc = to; T[to++] = EMP;
if(pi.lc == -1) add(EMP, T[ni.lc], s, m, L);
else add(T[pi.lc], T[ni.lc], s, m, L);
}
}
long long get(node id, int s, int e, int x) {
// printf("get: (%lld, %lld)\n", id.l.A, id.l.B);
if(x < s || e < x) return INF;
int m = s+e >> 1;
long long ret = id.l.get(x);
if(id.lc != -1) ret = min(ret, get(T[id.lc], s, m, x));
if(id.rc != -1) ret = min(ret, get(T[id.rc], m, e, x));
return ret;
}
long long D[100009];
int S[100009], V[100009];
vector<pii> adj[100009];
void dfs(int x, int p, int de) {
if(x != 1) D[x] = get(T[root[p]], 1, iNF, V[x]) + 1LL*de*V[x] + S[x];
root[x] = to; T[to++] = EMP;
add(T[root[p]], T[root[x]], 1, iNF, {-de, D[x]});
for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, de + it.second);
}
int main() {
int N; scanf("%d",&N);
for(int i=0; i<N-1; i++) {
int u, v, w; scanf("%d%d%d",&u,&v,&w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(int i=2; i<=N; i++) scanf("%d%d",&S[i],&V[i]);
T[to++] = EMP;
dfs(1, 0, 0);
for(int i=2; i<=N; i++) printf("%lld ", D[i]);
return 0;
}
Compilation message
harbingers.cpp: In function 'void add(node, node&, int, int, line)':
harbingers.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
harbingers.cpp: In function 'long long int get(node, int, int, int)':
harbingers.cpp:45:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
harbingers.cpp:66:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d%d%d",&u,&v,&w);
~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:31: 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("%d%d",&S[i],&V[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3192 KB |
Output is correct |
| 3 |
Runtime error |
98 ms |
36472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
106 ms |
36732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Correct |
136 ms |
19900 KB |
Output is correct |
| 6 |
Correct |
160 ms |
19064 KB |
Output is correct |
| 7 |
Correct |
113 ms |
16888 KB |
Output is correct |
| 8 |
Runtime error |
145 ms |
41336 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
144 ms |
41880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
132 ms |
41740 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
