Submission #68670

#	Time	Username	Problem	Language	Result	Execution time	Memory
68670		IvanC	Election Campaign (JOI15_election_campaign)	C++17	20 / 100	1085 ms	29556 KiB

election_campaign

#include <bits/stdc++.h>
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];

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];
}

int query_up(int v,int alvo){
	int ans = 0;
	if(v == alvo) return 0;
	while(v != alvo){
		ans +=  tab[v][0] - tab[v][1];
		v = pai[v]; 
	}
	return ans;
}

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];
		//printf("LCA %d de %d %d com %d\n",v,u,w,x);
		best_delta = max(best_delta, query_up(u,v) + query_up(w,v) + x );
	}

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

	//printf("V %d T0 %d BD %d\n",v,temp0,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: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:100: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:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&M);
  ~~~~~^~~~~~~~~
election_campaign.cpp:110: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: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40