| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122443 |
2019-06-28T08:33:43 Z |
윤교준(#2990) |
Robots (APIO13_robots) |
C++14 |
|
6 ms |
5120 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 200055;
ll D[MAXN], E[MAXN], F[MAXN];
vector<int> G[MAXN];
int prt[MAXN], prte[MAXN], dep[MAXN];
int A[MAXN], B[MAXN], C[MAXN];
int N;
void f(int i) {
D[i] = E[i] = F[i] = -INFLL;
if(G[i].empty()) {
E[i] = 0;
return;
}
F[i] = E[i] = 0;
for(int e : G[i]) {
int v = A[e]^B[e]^i;
f(v);
E[i] += max({D[v], E[v], F[v] + C[e]});
}
int dg = sz(G[i]);
for(int a = 0; a < dg; a++) {
ll ret= 0;
int ea = G[i][a];
int va = A[ea]^B[ea]^i;
ret += C[ea]; ret += max(D[va], E[va]);
for(int c = 0; c < dg; c++) {
if(a == c) continue;
int e = G[i][c];
int v = A[e]^B[e]^i;
ret += max({D[v], E[v], F[v] + C[e]});
}
upmax(F[i], ret);
}
for(int a = 0; a < dg; a++) for(int b = a+1; b < dg; b++) {
ll ret = 0;
int ea = G[i][a], eb = G[i][b];
int va = A[ea]^B[ea]^i, vb = A[eb]^B[eb]^i;
ret += C[ea]; ret += C[eb];
ret += max(D[va], E[va]) + max(D[vb], E[vb]);
for(int c = 0; c < dg; c++) {
if(a == c || b == c) continue;
int e = G[i][c];
int v = A[e]^B[e]^i;
ret += max({D[v], E[v], F[v] + C[e]});
}
upmax(D[i], ret);
}
}
void predfs(int i) {
for(int e : G[i]) {
int v = A[e]^B[e]^i;
if(dep[v]) continue;
dep[v] = dep[i] + 1;
prt[v] = i;
prte[v] = e;
predfs(v);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i < N; i++) {
cin >> A[i] >> B[i] >> C[i];
G[A[i]].eb(i);
G[B[i]].eb(i);
}
dep[1] = 1; predfs(1);
for(int i = 2; i <= N; i++)
G[i].erase(find(allv(G[i]), prte[i]));
f(1);
/*
for(int i = 1; i <= N; i++)
printf("%d ; %lld %lld %lld\n", i, D[i], E[i], F[i]);
*/
cout << max({D[1], E[1]}) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
