Submission #36012

#	Time	Username	Problem	Language	Result	Execution time	Memory
36012		ngkan146	Election Campaign (JOI15_election_campaign)	C++98	100 / 100	646 ms	38688 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct query{
	int a,b,val;
	query(int a=0,int b=0,int val=0): a(a), b(b), val(val) {}
};
int n,m,lv[100005], beg[100005], fin[100005], p[100005][20], ___time;
vector <int> G[100005];
vector <query> Q[100005];
void dfs(int u){
	for(int k=1;k<20;k++)
		p[u][k] = p[p[u][k-1]][k-1];
	beg[u] = ++___time;
	for(int i=0;i<(int)G[u].size();i++){
		int v = G[u][i];
		if (v == p[u][0]) continue;
		p[v][0] = u;
		lv[v] = lv[u]+1;
		dfs(v);
	}
	fin[u] = ___time;
}
int lca(int x,int y){
	for(int k=19;k>=0;k--)	if (lv[p[x][k]] >= lv[y]) x = p[x][k];
	for(int k=19;k>=0;k--)	if (lv[p[y][k]] >= lv[x]) y = p[y][k];
	if (x == y) return x;
	for(int k=19;k>=0;k--)	if (p[x][k] != p[y][k])	x = p[x][k], y = p[y][k];
	return p[x][0];
}
ll seg[400005], lazy[400005];
void _lazy(int id,int l,int r){
	seg[id] += lazy[id] * (r - l + 1);
	if (l != r){
		lazy[2*id] += lazy[id];
		lazy[2*id+1] += lazy[id];
	}
	lazy[id] = 0;
}
void seg_upd(int id,int l,int r,int u,int v,ll val){
	_lazy(id,l,r);
	if (r < u || v < l) return;
	if (u <= l && r <= v){
		lazy[id] += val;
		_lazy(id,l,r);
		return;
	}
	seg_upd(2*id, l, (l+r)/2, u, v, val);
	seg_upd(2*id+1, (l+r)/2+1, r, u, v, val);
	seg[id] = seg[2*id] + seg[2*id+1];
}
ll seg_get(int id,int l,int r,int pos){
	_lazy(id,l,r);
	if (r < pos || pos < l)		return 0;
	if (l == r)	return seg[id];
	return seg_get(2*id, l, (l+r)/2, pos) + seg_get(2*id+1, (l+r)/2+1, r, pos);
}
ll dp[100005];
ll get_decendant(int x,int y){
	int l = 0, r = G[x].size();
	while(l+1 < r){
		int mid = (l+r)/2;
		int z = G[x][mid];
		if (beg[y] < beg[z])	r = mid;
		else l = mid; 
	}
	return G[x][l];
}
void solve(int u){
	ll sum = 0;
	//cout << u << ' ' << p[u][0] << endl;
	for(int i=0;i<(int)G[u].size();i++){
		if (G[u][i] != p[u][0])	
			solve(G[u][i]), 
			sum += dp[G[u][i]];
	}
	
	dp[u] = sum;
	for(int id=0;id<(int)Q[u].size();id++){
		int a = Q[u][id].a;
		int b = Q[u][id].b;
		int val = Q[u][id].val;
		//cout << "Q" << u << ' ' << a << ' ' << b << endl;
		if (a == u)
			dp[u] = max(dp[u], seg_get(1,1,n,beg[b]) + sum - dp[get_decendant(u,b)] + val); 
		else if (b == u)
			dp[u] = max(dp[u], seg_get(1,1,n,beg[a]) + sum - dp[get_decendant(u,a)] + val);
		else
			dp[u] = max(dp[u], sum + seg_get(1,1,n,beg[a]) + seg_get(1,1,n,beg[b]) - dp[get_decendant(u,a)] - dp[get_decendant(u,b)] + val);
	}
	for(int i=0;i<(int)G[u].size();i++){
		int v = G[u][i];
		if (v == p[u][0]) continue;
		seg_upd(1,1,n,beg[v],fin[v], sum - dp[v]);
	}
	seg_upd(1,1,n,beg[u],beg[u], sum);
	//cout << "res " << u << ' ' << dp[u] << endl;
	
}
bool cmp(int x,int y){
	return beg[x] < beg[y];
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	lv[1] = 1;
	dfs(1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int a,b,val;
		scanf("%d %d %d",&a,&b,&val);
		Q[lca(a,b)].push_back(query(a,b,val));
	}
	for(int i=1;i<=n;i++)	sort(G[i].begin(), G[i].end(), cmp);
	solve(1);
	cout << dp[1];
}
/*
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
*/

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:104:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
election_campaign.cpp:107:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^
election_campaign.cpp:113:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
election_campaign.cpp:116:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&val);
                               ^

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