# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
103607 | 2019-03-31T23:03:06 Z | luciocf | Election Campaign (JOI15_election_campaign) | C++14 | 290 ms | 20892 KB |
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int n, m; int A[maxn], B[maxn], C[maxn]; int nivel[maxn], pai[maxn], sz[maxn]; int chain[maxn], head[maxn], pos[maxn]; int cc, pp; int bit[maxn]; int dp[maxn]; vector<int> grafo[maxn], op[maxn]; void upd(int x, int v) { for (; x < maxn; x += (x&-x)) bit[x] += v; } int soma(int x) { int ans = 0; for (; x > 0; x -= (x&-x)) ans += bit[x]; return ans; } void dfs(int u, int p) { sz[u] = 1; for (auto v: grafo[u]) { if (v == p) continue; pai[v] = u, nivel[v] = nivel[u]+1; dfs(v, u); sz[u] += sz[v]; } } void hld(int u) { if (!head[cc]) head[cc] = u; chain[u] = cc, pos[u] = ++pp; int maior = -1, ind = -1; for (auto v: grafo[u]) if (v != pai[u] && sz[v] > maior) maior = sz[v], ind = v; if (ind != -1) hld(ind); for (auto v: grafo[u]) if (v != pai[u] && v != ind) cc++, hld(v); } int lca(int u, int v) { while (chain[u] != chain[v]) { if (nivel[head[chain[u]]] > nivel[head[chain[v]]]) u = pai[head[chain[u]]]; else v = pai[head[chain[v]]]; } if (nivel[u] > nivel[v]) return v; return u; } int query(int u, int v) { int ans = 0; while (true) { if (chain[u] == chain[v]) return ans+soma(pos[u])-soma(pos[v]); ans += soma(pos[u])-soma(pos[head[chain[u]]]-1); u = pai[head[chain[u]]]; } } int solve(int u, int p) { int ans = 0; for (auto v: grafo[u]) { if (v == p) continue; solve(v, u); ans += dp[v]; } dp[u] = ans; int cur = 0; for (auto i: op[u]) { int a = A[i], b = B[i], c = C[i]; int x = query(a, u) + query(b, u); if (ans-x+c > dp[u] || (ans-x+c == dp[u] && c < cur)) { dp[u] = ans-x+c; upd(pos[u], c-cur); cur = c; } } } int main(void) { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); grafo[u].push_back(v); grafo[v].push_back(u); } dfs(1, 0); hld(1); scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &A[i], &B[i], &C[i]); op[lca(A[i], B[i])].push_back(i); } solve(1, 0); printf("%d\n", dp[1]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 7 ms | 5120 KB | Output is correct |
3 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 7 ms | 5248 KB | Output is correct |
4 | Correct | 115 ms | 20828 KB | Output is correct |
5 | Correct | 116 ms | 20892 KB | Output is correct |
6 | Correct | 106 ms | 20792 KB | Output is correct |
7 | Correct | 108 ms | 20648 KB | Output is correct |
8 | Correct | 115 ms | 20660 KB | Output is correct |
9 | Correct | 128 ms | 20696 KB | Output is correct |
10 | Correct | 113 ms | 20716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 7 ms | 5248 KB | Output is correct |
4 | Correct | 115 ms | 20828 KB | Output is correct |
5 | Correct | 116 ms | 20892 KB | Output is correct |
6 | Correct | 106 ms | 20792 KB | Output is correct |
7 | Correct | 108 ms | 20648 KB | Output is correct |
8 | Correct | 115 ms | 20660 KB | Output is correct |
9 | Correct | 128 ms | 20696 KB | Output is correct |
10 | Correct | 113 ms | 20716 KB | Output is correct |
11 | Incorrect | 17 ms | 5760 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 233 ms | 12916 KB | Output is correct |
2 | Correct | 108 ms | 20728 KB | Output is correct |
3 | Correct | 200 ms | 17940 KB | Output is correct |
4 | Correct | 149 ms | 13224 KB | Output is correct |
5 | Correct | 290 ms | 17540 KB | Output is correct |
6 | Correct | 154 ms | 13216 KB | Output is correct |
7 | Correct | 232 ms | 17272 KB | Output is correct |
8 | Correct | 239 ms | 13384 KB | Output is correct |
9 | Correct | 111 ms | 20728 KB | Output is correct |
10 | Correct | 190 ms | 16284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 7 ms | 5120 KB | Output is correct |
3 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 7 ms | 5120 KB | Output is correct |
3 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |