oj.uz

Submission #68670

# Submission time Handle Problem Language Result Execution time Memory
68670 2018-08-17T22:20:17 Z IvanC Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 29556 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5172 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 99 ms 18688 KB Output is correct
6 Correct 69 ms 26388 KB Output is correct
7 Correct 106 ms 26388 KB Output is correct
8 Correct 89 ms 26388 KB Output is correct
9 Correct 112 ms 26388 KB Output is correct
10 Correct 75 ms 26388 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26388 KB Output is correct
2 Correct 6 ms 26388 KB Output is correct
3 Correct 7 ms 26388 KB Output is correct
4 Execution timed out 1085 ms 29388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26388 KB Output is correct
2 Correct 6 ms 26388 KB Output is correct
3 Correct 7 ms 26388 KB Output is correct
4 Execution timed out 1085 ms 29388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 29388 KB Output is correct
2 Execution timed out 1064 ms 29556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5172 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 99 ms 18688 KB Output is correct
6 Correct 69 ms 26388 KB Output is correct
7 Correct 106 ms 26388 KB Output is correct
8 Correct 89 ms 26388 KB Output is correct
9 Correct 112 ms 26388 KB Output is correct
10 Correct 75 ms 26388 KB Output is correct
11 Correct 7 ms 29556 KB Output is correct
12 Correct 9 ms 29556 KB Output is correct
13 Correct 9 ms 29556 KB Output is correct
14 Correct 9 ms 29556 KB Output is correct
15 Correct 7 ms 29556 KB Output is correct
16 Correct 7 ms 29556 KB Output is correct
17 Correct 7 ms 29556 KB Output is correct
18 Correct 9 ms 29556 KB Output is correct
19 Correct 9 ms 29556 KB Output is correct
20 Correct 9 ms 29556 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5172 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 99 ms 18688 KB Output is correct
6 Correct 69 ms 26388 KB Output is correct
7 Correct 106 ms 26388 KB Output is correct
8 Correct 89 ms 26388 KB Output is correct
9 Correct 112 ms 26388 KB Output is correct
10 Correct 75 ms 26388 KB Output is correct
11 Correct 6 ms 26388 KB Output is correct
12 Correct 6 ms 26388 KB Output is correct
13 Correct 7 ms 26388 KB Output is correct
14 Execution timed out 1085 ms 29388 KB Time limit exceeded
15 Halted 0 ms 0 KB -