# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
550712 | 2022-04-18T21:26:29 Z | nafis_shifat | Election Campaign (JOI15_election_campaign) | C++17 | 1000 ms | 53080 KB |
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; const int mxn=3e5+5; const ll inf=1e15; int n; vector<int> adj[mxn]; int level[mxn] = {}; int pa[18][mxn] = {}; int in[mxn] = {}; int T = 0; int out[mxn]; int q; vector<tuple<int,int,int>> con[mxn]; void dfs0(int u,int prev) { level[u] = level[prev]+1; pa[0][u] = prev; for(int i = 1; i < 18; i++) pa[i][u] = pa[i - 1][pa[i - 1][u]]; for(int v : adj[u]) { if(v == prev) continue; dfs0(v,u); } } int findLCA(int u,int v) { if(level[u] < level[v]) swap(u,v); int diff = level[u] - level[v]; for(int i = 0;i < 18;i++) if((diff>>i)&1) u = pa[i][u]; if(u == v) return u; for(int i = 17; i >= 0; i--) { if(pa[i][u] != pa[i][v]){ u = pa[i][u]; v = pa[i][v]; } } return pa[0][u]; } ll dp[mxn] = {}; ll child_sum[mxn] = {}; ll tot[18][mxn]; ll TOT(int i, int x) { if(tot[i][x] != -inf) return tot[i][x]; return TOT(i - 1, x) + TOT(i - 1, pa[i - 1][x]); } ll get(int x, int dif) { ll sum = 0; for(int i = 17; i >= 0; i--) { if((dif >> i) & 1) { sum += TOT(i, x); x = pa[i][x]; } } return sum; } void dfs(int u, int prev) { for(int v : adj[u]) { if(v == prev) continue; dfs(v, u); child_sum[u] += dp[v]; } dp[u] = child_sum[u]; for(auto [a, b, c] : con[u]) { dp[u] = max(dp[u], get(a, level[a] - level[u]) + get(b, level[b] - level[u]) + c + child_sum[u]); } tot[0][u] = child_sum[u] - dp[u]; } int main() { cin >> n; for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } dfs0(1, 0); for(int i = 0; i < 18; i++) for(int j = 1; j <= n; j++) tot[i][j] = -inf; cin >> q; for(int i = 1; i <= q; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); con[findLCA(a, b)].push_back({a, b, c}); } dfs(1, 0); cout<<dp[1]<<endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14676 KB | Output is correct |
2 | Correct | 8 ms | 14676 KB | Output is correct |
3 | Correct | 7 ms | 14576 KB | Output is correct |
4 | Correct | 8 ms | 14940 KB | Output is correct |
5 | Correct | 85 ms | 40988 KB | Output is correct |
6 | Correct | 53 ms | 48664 KB | Output is correct |
7 | Correct | 105 ms | 46004 KB | Output is correct |
8 | Correct | 97 ms | 40596 KB | Output is correct |
9 | Correct | 86 ms | 44332 KB | Output is correct |
10 | Correct | 75 ms | 40636 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14676 KB | Output is correct |
2 | Correct | 7 ms | 14676 KB | Output is correct |
3 | Correct | 9 ms | 14932 KB | Output is correct |
4 | Execution timed out | 1080 ms | 50416 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14676 KB | Output is correct |
2 | Correct | 7 ms | 14676 KB | Output is correct |
3 | Correct | 9 ms | 14932 KB | Output is correct |
4 | Execution timed out | 1080 ms | 50416 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 173 ms | 42504 KB | Output is correct |
2 | Execution timed out | 1091 ms | 53080 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14676 KB | Output is correct |
2 | Correct | 8 ms | 14676 KB | Output is correct |
3 | Correct | 7 ms | 14576 KB | Output is correct |
4 | Correct | 8 ms | 14940 KB | Output is correct |
5 | Correct | 85 ms | 40988 KB | Output is correct |
6 | Correct | 53 ms | 48664 KB | Output is correct |
7 | Correct | 105 ms | 46004 KB | Output is correct |
8 | Correct | 97 ms | 40596 KB | Output is correct |
9 | Correct | 86 ms | 44332 KB | Output is correct |
10 | Correct | 75 ms | 40636 KB | Output is correct |
11 | Correct | 9 ms | 14932 KB | Output is correct |
12 | Correct | 11 ms | 14996 KB | Output is correct |
13 | Correct | 9 ms | 14932 KB | Output is correct |
14 | Correct | 10 ms | 14936 KB | Output is correct |
15 | Correct | 9 ms | 14920 KB | Output is correct |
16 | Correct | 10 ms | 14928 KB | Output is correct |
17 | Correct | 9 ms | 14876 KB | Output is correct |
18 | Correct | 9 ms | 14932 KB | Output is correct |
19 | Correct | 9 ms | 14928 KB | Output is correct |
20 | Correct | 10 ms | 14932 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 14676 KB | Output is correct |
2 | Correct | 8 ms | 14676 KB | Output is correct |
3 | Correct | 7 ms | 14576 KB | Output is correct |
4 | Correct | 8 ms | 14940 KB | Output is correct |
5 | Correct | 85 ms | 40988 KB | Output is correct |
6 | Correct | 53 ms | 48664 KB | Output is correct |
7 | Correct | 105 ms | 46004 KB | Output is correct |
8 | Correct | 97 ms | 40596 KB | Output is correct |
9 | Correct | 86 ms | 44332 KB | Output is correct |
10 | Correct | 75 ms | 40636 KB | Output is correct |
11 | Correct | 8 ms | 14676 KB | Output is correct |
12 | Correct | 7 ms | 14676 KB | Output is correct |
13 | Correct | 9 ms | 14932 KB | Output is correct |
14 | Execution timed out | 1080 ms | 50416 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |