| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130732 |
2019-07-16T04:22:07 Z |
이온조(#3169) |
Harbingers (CEOI09_harbingers) |
C++14 |
|
104 ms |
16632 KB |
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct line {
long long A, B;
long long get(int x) { return A*x + B; }
};
struct node {
int lc, rc;
line l;
};
const int iNF = 1e9;
const long long INF = 1LL * 1e18;
node EMP = {-1, -1, {0, INF}};
struct pslihao {
vector<node> T;
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 = T.size(); T.push_back(EMP);
if(pi.rc == -1) {
node tmp = EMP;
add(tmp, T[ni.rc], m, e, L);
}
else add(T[pi.rc], T[ni.rc], m, e, L);
}
else {
ni.lc = T.size(); T.push_back(EMP);
if(pi.lc == -1) {
node tmp = EMP;
add(tmp, 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;
}
pslihao() {
T.push_back(EMP);
}
} CH;
long long D[100009];
int S[100009], V[100009];
vector<pii> adj[100009];
void dfs(int x, int p, int de) {
// printf("x: %d, p: %d, de: %d\n", x, p ,de);
if(x != 1) D[x] = CH.get(CH.T[CH.root[p]], 1, iNF, V[x]) + 1LL*de*V[x] + S[x];
// printf("D[%d]: %lld\n", x, D[x]);
// puts("getted");
CH.root[x] = CH.T.size(); CH.T.push_back(EMP);
CH.add(CH.T[CH.root[p]], CH.T[CH.root[x]], 1, iNF, {-de, D[x]});
// puts("added");
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]);
dfs(1, 0, 0);
for(int i=2; i<=N; i++) printf("%lld ", D[i]);
return 0;
}
Compilation message
harbingers.cpp: In member function 'void pslihao::add(node&, node&, int, int, line)':
harbingers.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
harbingers.cpp: In member function 'long long int pslihao::get(node&, int, int, int)':
harbingers.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:79: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:81: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:85: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 |
Runtime error |
11 ms |
6328 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
47 ms |
9936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
60 ms |
11704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
84 ms |
14372 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
100 ms |
16632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
69 ms |
13256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
104 ms |
15720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
103 ms |
15984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
91 ms |
16024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
