oj.uz

답안 #122443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122443 2019-06-28T08:33:43 Z 윤교준(#2990) 로봇 (APIO13_robots) C++14
0 / 100
 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;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -