Submission #68671

#	Time	Username	Problem	Language	Result	Execution time	Memory
68671		IvanC	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	425 ms	33228 KiB

election_campaign

#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;

const int MAXN = 1e5 + 10;
const int MAXL = 20;

vector<int> grafo[MAXN],perguntas[MAXN];
int N,M,tab[MAXN][2],pai[MAXN],nivel[MAXN],ini[MAXN],fim[MAXN],dfsPtr,e1[MAXN],e2[MAXN],e3[MAXN];
int ancestral[MAXN][MAXL];
long long bit[MAXN];

void update_bit(int pos,int delta){
	while(pos <= N){
		bit[pos] += delta;
		pos += LSOne(pos);
	}
}

long long read(int pos){

	long long ans = 0;
	while(pos > 0){
		ans += bit[pos];
		pos -= LSOne(pos);
	}

	return ans;

}

void dfs_build(int v,int p){

	pai[v] = p;
	nivel[v] = nivel[p] + 1;
	ini[v] = ++dfsPtr;

	for(int u : grafo[v]){
		if(u == p) continue;
		dfs_build(u,v);
	}

	fim[v] = dfsPtr;

}

void build_lca(){
	for(int i = 1;i<=N;i++) ancestral[i][0] = pai[i];

	for(int j = 1;j<MAXL;j++){
		for(int i = 1;i<=N;i++){
			int z = ancestral[i][j-1];
			if(z == 0) ancestral[i][j] = 0;
			else ancestral[i][j] = ancestral[z][j-1];
		}
	}

}

int LCA(int u,int v){

	if(nivel[u] < nivel[v]) swap(u,v);

	for(int i = MAXL - 1;i>=0;i--){
		int z = ancestral[u][i];
		if(nivel[z] >= nivel[v]){
			u = z;
		}
	}

	if(u == v) return u;

	for(int i = MAXL - 1;i>=0;i--){
		if(ancestral[u][i] != ancestral[v][i] && ancestral[u][i] != -1){
			u = ancestral[u][i];
			v = ancestral[v][i];
		}
	}

	return pai[u];
}

void dfs_ans(int v,int p){

	int temp0 = 0, best_delta = 0;

	for(int u : grafo[v]){
		if(u == p) continue;
		dfs_ans(u,v);
		temp0 += tab[u][1];
	}

	for(int i : perguntas[v]){
		int u = e1[i],w = e2[i],x = e3[i];
		long long meu_delta = 0;
		if(u != v) meu_delta += read(ini[u]);
		if(w != v) meu_delta += read(ini[w]);
		best_delta = max(best_delta, int(meu_delta + x) );
	}

	tab[v][0] = temp0;
	tab[v][1] = temp0 + best_delta;

	update_bit(ini[v], -best_delta);
	update_bit(fim[v] + 1, best_delta);

}

int main(){

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

	dfs_build(1,0);
	build_lca();

	scanf("%d",&M);
	for(int i = 1;i<=M;i++){
		scanf("%d %d %d",&e1[i],&e2[i],&e3[i]);
		int ancestral = LCA(e1[i],e2[i]);
		perguntas[ancestral].push_back(i);
	}

	dfs_ans(1,0);

	printf("%d\n",max(tab[1][1],tab[1][0]));

	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
election_campaign.cpp:114: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:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&M);
  ~~~~~^~~~~~~~~
election_campaign.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&e1[i],&e2[i],&e3[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