oj.uz

Submission #30643

# Submission time Handle Problem Language Result Execution time Memory
30643 2017-07-25T20:01:12 Z ulna Beads and wires (APIO14_beads) C++11
0 / 100
 6 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n;

struct edge {int to; long long cost;};

vector<edge> g[200055];

inline void add_edge(int from, int to, int cost) {
	g[from].push_back((edge){to, cost});
}

long long dp[200055][2];

void dfs(int v, int par = -1) {
	dp[v][0] = 0;
	dp[v][1] = -(long long)1e13;
	
	// one dp[e.to][0] + e.cost
	
	long long sum = 0ll;

	for (auto e : g[v]) if (e.to != par) {
		dfs(e.to, v);

		dp[v][0] += max(dp[e.to][0], dp[e.to][1] + e.cost);
		sum += max(dp[e.to][0], dp[e.to][1] + e.cost);
	}

	for (auto e : g[v]) if (e.to != par) {
		dp[v][1] = max(dp[v][1], sum - max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}
}

struct dat {long long dat[2];};

long long rdfs(int v, int par, dat ac, long long cost) {
	long long res = dp[v][0] + max(ac.dat[0], ac.dat[1] + cost);

	dat cool;
	cool.dat[0] = 0;
	cool.dat[1] = -(long long)1e13;

	multiset<long long> s;
	long long sum = 0;

	for (auto e : g[v]) if (e.to != par) {
		cool.dat[0] += max(dp[e.to][0], dp[e.to][1] + e.cost);
		sum += max(dp[e.to][0], dp[e.to][1] + e.cost);
		
		s.insert(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}

	cool.dat[0] += max(ac.dat[0], ac.dat[1] + cost);
	sum += max(ac.dat[0], ac.dat[1] + cost);

	s.insert(-max(ac.dat[0], ac.dat[1] + cost) + ac.dat[0] + cost);

	for (auto e : g[v]) if (e.to != par) {
		s.erase(s.find(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost));

		cool.dat[0] -= max(dp[e.to][0], dp[e.to][1] + e.cost);
		cool.dat[1] = sum + *s.rbegin();

		res = max(res, rdfs(e.to, v, cool, e.cost));
		
		cool.dat[0] += max(dp[e.to][0], dp[e.to][1] + e.cost);

		s.insert(-max(dp[e.to][0], dp[e.to][1] + e.cost) + dp[e.to][0] + e.cost);
	}

	return res;
}
int main() {
	scanf("%d", &n);

	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		x--, y--;

		add_edge(x, y, z);
		add_edge(y, x, z);
	}

	dfs(0);

	dat a;
	a.dat[0] = 0;
	a.dat[1] = -(long long)1e13;
	
	printf("%lld\n", rdfs(0, -1, a, -(long long)1e13));

	return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Incorrect 6 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Incorrect 6 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Incorrect 6 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Incorrect 6 ms 4992 KB Output isn't correct
3 Halted 0 ms 0 KB -