Submission #223671

#	Time	Username	Problem	Language	Result	Execution time	Memory
223671		arnold518	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	325 ms	41048 KiB

election_campaign

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, Q;
vector<int> adj[MAXN+10];

int par[MAXN+10][25];
int dep[MAXN+10];
int L[MAXN+10], R[MAXN+10], cnt;

struct Query
{
	int u, v, w;
};
vector<Query> A[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	par[now][0]=bef;
	L[now]=++cnt;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
	R[now]=cnt;
}

int lca(int x, int y)
{
	int i, j;
	if(dep[x]<dep[y]) swap(x, y);
	for(i=20; i>=0; i--) if(dep[par[x][i]]>=dep[y]) x=par[x][i];
	if(x==y) return x;
	for(i=20; i>=0; i--) if(par[x][i]!=par[y][i]) x=par[x][i], y=par[y][i];
	return par[x][0];
}

struct SEG
{
	int tree[MAXN*4+10];
	void update(int node, int tl, int tr, int l, int r, int k)
	{
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r) { tree[node]+=k; return; }
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	int query(int node, int tl, int tr, int p)
	{
		if(tl==tr) return tree[node];
		int mid=tl+tr>>1;
		if(p<=mid) return tree[node]+query(node*2, tl, mid, p);
		else return tree[node]+query(node*2+1, mid+1, tr, p);
	}
} seg;
int dp[MAXN+10];

void dfs2(int now, int bef)
{
	int i, j;	
	vector<int> chd;

	int sum=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now);
		chd.push_back(nxt);
		sum+=dp[nxt];
	}

	dp[now]=sum;

	for(auto nxt : chd) seg.update(1, 1, N, L[nxt], R[nxt], -dp[nxt]);	
	for(auto &it : A[now])
	{
		int v=seg.query(1, 1, N, L[it.u])+seg.query(1, 1, N, L[it.v])+sum+it.w;
		dp[now]=max(dp[now], v);
	}

	seg.update(1, 1, N, L[now], R[now], sum);
}

int main()
{
	int i, j;

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

	dfs(1, 1, 1);
	for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	scanf("%d", &Q);
	while(Q--)
	{
		int u, v, w, k;
		scanf("%d%d%d", &u, &v, &k);
		w=lca(u, v);
		A[w].push_back({u, v, k});
	}

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

Compilation message (stderr)

election_campaign.cpp: In function 'int lca(int, int)':
election_campaign.cpp:38:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
election_campaign.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
election_campaign.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
election_campaign.cpp: In member function 'int SEG::query(int, int, int, int)':
election_campaign.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
election_campaign.cpp: In function 'void dfs2(int, int)':
election_campaign.cpp:69:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j; 
      ^
election_campaign.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j; 
         ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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