Submission #54635

#	Time	Username	Problem	Language	Result	Execution time	Memory
54635		ikura355	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	451 ms	152572 KiB

election_campaign

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

const int maxn = 1e5 + 5;
const int mlog = 17;

int n,m;
vector<int> way[maxn];
vector<tuple<int,int,int>> have[maxn];

int cur, st[maxn], ft[maxn];

int h[maxn], par[maxn][20];

int tree[maxn*4];

int dp[maxn];

void dfs(int u, int last) {
	st[u] = ++cur;

	h[u] = h[last] + 1;
	par[u][0] = last;
	for(int i=1;i<=mlog;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto v : way[u]) {
		if(v==last) continue;
		dfs(v,u);
	}

	ft[u] = cur;
}

int lca(int u, int v) {
	if(h[u]<h[v]) swap(u,v);
	for(int i=mlog;i>=0;i--) if(h[par[u][i]]>=h[v]) u = par[u][i];
	if(u==v) return u;
	for(int i=mlog;i>=0;i--) {
		if(par[u][i]!=par[v][i]) {
			u = par[u][i]; v = par[v][i];
		}
	}
	return par[u][0];
}

void update(int pos, int l, int r, int x, int y, int val) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		tree[pos] += val;
		return ;
	}
	int mid = (l+r)/2;
	update(pos<<1,l,mid,x,y,val); update(pos<<1|1,mid+1,r,x,y,val);
}

int query(int pos, int l, int r, int x) {
	if(l>r || r<x || x<l) return 0;
	if(l==r) return tree[pos];
	int mid = (l+r)/2;
	return tree[pos] + query(pos<<1,l,mid,x) + query(pos<<1|1,mid+1,r,x);
}

void solve(int u, int last) {
	int sum = 0;
	//solve child
	for(auto v : way[u]) {
		if(v==last) continue;
		solve(v, u);
		sum += dp[v];
	}
	//solve u
	dp[u] = sum;
	for(auto t : have[u]) {
		int x,y,val;
		tie(x,y,val) = t;
		int change = query(1,1,n,st[x]) + query(1,1,n,st[y]);
		dp[u] = max(dp[u], sum + val + change);
	}
	//update subtree u
	update(1,1,n,st[u],ft[u],-dp[u]+sum);
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back(v); way[v].push_back(u);
	}

	dfs(1,0);

	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		int u,v,val; scanf("%d%d%d",&u,&v,&val);
		have[lca(u,v)].emplace_back(u,v,val);
	}

	solve(1,0);

	printf("%d",dp[1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
election_campaign.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
election_campaign.cpp:93:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v,val; scanf("%d%d%d",&u,&v,&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