Submission #36101

#	Time	Username	Problem	Language	Result	Execution time	Memory
36101		UncleGrandpa925	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	756 ms	78248 KiB

election_campaign

/*input
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 100005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct data {
	int u, v, w;
	data(int _u, int _v, int _w): u(_u), v(_v), w(_w) {};
};

int n, m;
vector<vector<int> > a(N);
vector<vector<int> > b(N);
vector<vector<data> > go(N);

int par[N][22];
int dis[N];
int sta[N], en[N], Time = 0;

void dfs(int u, int p) {
	par[u][0] = p; sta[u] = ++Time;
	for (int i = 0; i < a[u].size(); i++) {
		int v = a[u][i];
		if (v != p) {
			b[u].push_back(v);
			dis[v] = dis[u] + 1;
			dfs(v, u);
		}
	}
	en[u] = Time;
}

int lca(int p, int q) {
	if (dis[p] < dis[q]) swap(p, q);
	for (int i = 20; i >= 0; i--) {
		if (dis[par[p][i]] >= dis[q]) {
			p = par[p][i];
		}
	}
	if (p == q) return p;
	for (int i = 20; i >= 0; i--) {
		if (par[p][i] != par[q][i]) {
			p = par[p][i];
			q = par[q][i];
		}
	}
	return par[p][0];
}

void makelca() {
	dfs(1, 1);
	for (int i = 1; i <= 20; i++) {
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
		}
	}
}

class ITrangeSum {
private:
	int f[4 * N];
	int lazy[4 * N];
	void dolazy(int k, int l, int r) {
		if (lazy[k] == 0) return;
		f[k] += lazy[k] * (r - l + 1);
		if (l != r) {
			lazy[k * 2] += lazy[k];
			lazy[k * 2 + 1] += lazy[k];
		}
		lazy[k] = 0;
	}
public:
	void update(int k, int l, int r, int L, int R, int val) {
		dolazy(k, l, r);
		if (r < L || R < l) return;
		if (L <= l && r <= R) {
			f[k] += val * (r - l + 1);
			if (l != r) {
				lazy[k * 2] += val;
				lazy[k * 2 + 1] += val;
			}
			return;
		}
		int mid = (l + r) / 2;
		update(k * 2, l, mid, L, R, val); update(k * 2 + 1, mid + 1, r, L, R, val);
		f[k] = f[k * 2] + f[k * 2 + 1];
	}
	int get(int k, int l, int r, int L, int R) {
		dolazy(k, l, r);
		if (r < L || R < l) return 0;
		if (L <= l && r <= R) return f[k];
		int mid = (l + r) / 2;
		return get(k * 2, l, mid, L, R) + get(k * 2 + 1, mid + 1, r, L, R);
	}
} IT;

int getDescendant(int u, int v) {
	int l = 0, r = a[u].size() - 1;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (sta[a[u][mid]] <= sta[v]) l = mid;
		else r = mid - 1;
	}
	return a[u][l];
}

int dp[N];
void solve(int u) {
	int sum = 0;
	for (auto v : a[u]) {
		solve(v);
		sum += dp[v];
	}
	dp[u] = sum;
	for (int i = 0; i < go[u].size(); i++) {
		int fl = go[u][i].u; int fr = go[u][i].v; int w = go[u][i].w;
		if (fl == u) dp[u] = max(dp[u], sum - dp[getDescendant(u, fr)] + IT.get(1, 1, n, sta[fr], sta[fr]) + w);
		else if (fr == u) dp[u] = max(dp[u], sum - dp[getDescendant(u, fl)] + IT.get(1, 1, n, sta[fl], sta[fl]) + w);
		else dp[u] = max(dp[u], sum - dp[getDescendant(u, fr)] - dp[getDescendant(u, fl)] + IT.get(1, 1, n, sta[fl], sta[fl]) + IT.get(1, 1, n, sta[fr], sta[fr]) + w);
	}
	for (auto v : a[u]) 
		IT.update(1, 1, n, sta[v], en[v], sum - dp[v]);
	IT.update(1, 1, n, sta[u], sta[u], sum);
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		a[u].push_back(v); a[v].push_back(u);
	}
	makelca();
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		go[lca(u, v)].push_back(data(u, v, w));
	}
	a.swap(b);
	solve(1);
	cout << dp[1] << endl;
}

Compilation message (stderr)

election_campaign.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
election_campaign.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
election_campaign.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
election_campaign.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a[u].size(); i++) {
                    ^
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < go[u].size(); i++) {
                    ^

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40