Submission #1283210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283210		thuhienne	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	206 ms	27900 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100009;
const int LOG = 16;

long long fenchild[maxn],fennode[maxn];

void update(long long fen[],int pos,int val) {
	for (;pos <= 100003;pos += (pos & -pos)) fen[pos] += val;
}
void update(long long fen[],int l,int r,int val) {
	update(fen,l,val);
	update(fen,r + 1,-val);
}
long long get(long long fen[],int pos) {
	long long ret = 0;
	for (;pos;pos -= (pos & -pos)) ret += fen[pos];
	return ret;
}

#define re exit(0);
#define thuhien "JOI15_election_campaign"

int n,m;
vector <int> adj[maxn];

int tin[maxn],tout[maxn],timedfs,up[maxn][LOG + 1],h[maxn];

void predfs(int node,int par) {
	tin[node] = ++timedfs;
	for (auto x : adj[node]) if (x != par) {
		h[x] = h[node] + 1;
		up[x][0] = node;
		for (int i = 1;i <= LOG;i++) up[x][i] = up[up[x][i - 1]][i - 1];
		predfs(x,node);
	}
	tout[node] = timedfs;
}
int lca(int u,int v) {
	if (h[u] < h[v]) swap(u,v);
	int diff = h[u] - h[v];
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) u = up[u][i];
	if (u == v) return u;
	for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
		u = up[u][i];
		v = up[v][i];
	}
	return up[u][0];
}
long long getpath(long long fen[],int u,int v,int lca) {
	return get(fen,tin[u]) + get(fen,tin[v]) - get(fen,tin[lca]) - (lca == 1 ? 0 : get(fen,tin[up[lca][0]]));
}

struct election {
	int u,v,gain;
};

vector <election> path[maxn];

int dp[maxn];

void dfs(int node,int par) {
	//base case: dp node = sum(dp child)
	for (auto x : adj[node]) if (x != par) {
		dfs(x,node);
		dp[node] += dp[x];
	}
	update(fenchild,tin[node],tout[node],dp[node]);
	//trasition: su dung mot trong cac duong di trong path
	for (auto FUCK : path[node]) {
		int u = FUCK.u,v = FUCK.v,gain = FUCK.gain;
		long long d1 = getpath(fenchild,u,v,node);
		long long d2 = getpath(fennode,u,v,node);
		dp[node] = max(1ll*dp[node],d1 - d2 + gain);
	}
	update(fennode,tin[node],tout[node],dp[node]);
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
		freopen(thuhien".inp","r",stdin);
		freopen(thuhien".out","w",stdout);
	}

	cin >> n;
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	predfs(1,-1);
	
	cin >> m;
	for (int i = 1;i <= m;i++) {
		int u,v,c;cin >> u >> v >> c;
		if (h[u] > h[v]) swap(u,v);
		path[lca(u,v)].push_back({u,v,c});
	}
	
	dfs(1,-1);
	cout << dp[1];
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:83:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 freopen(thuhien".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:84:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |                 freopen(thuhien".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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