oj.uz

Submission #68669

# Submission time Handle Problem Language Result Execution time Memory
68669 2018-08-17T22:15:25 Z IvanC Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 25736 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

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

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;

}

int LCA(int u,int v){
	while(u != v){
		if(nivel[u] < nivel[v]) swap(u,v);
		u = pai[u];
	}
	return 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);

	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:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
election_campaign.cpp:70: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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&M);
  ~~~~~^~~~~~~~~
election_campaign.cpp:79: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 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5180 KB Output is correct
4 Correct 8 ms 5188 KB Output is correct
5 Correct 142 ms 12028 KB Output is correct
6 Correct 58 ms 20748 KB Output is correct
7 Correct 94 ms 20748 KB Output is correct
8 Correct 87 ms 20748 KB Output is correct
9 Correct 132 ms 20748 KB Output is correct
10 Correct 85 ms 20748 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20748 KB Output is correct
2 Correct 7 ms 20748 KB Output is correct
3 Correct 9 ms 20748 KB Output is correct
4 Execution timed out 1088 ms 24636 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20748 KB Output is correct
2 Correct 7 ms 20748 KB Output is correct
3 Correct 9 ms 20748 KB Output is correct
4 Execution timed out 1088 ms 24636 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 24636 KB Output is correct
2 Execution timed out 1092 ms 25736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5180 KB Output is correct
4 Correct 8 ms 5188 KB Output is correct
5 Correct 142 ms 12028 KB Output is correct
6 Correct 58 ms 20748 KB Output is correct
7 Correct 94 ms 20748 KB Output is correct
8 Correct 87 ms 20748 KB Output is correct
9 Correct 132 ms 20748 KB Output is correct
10 Correct 85 ms 20748 KB Output is correct
11 Correct 8 ms 25736 KB Output is correct
12 Correct 9 ms 25736 KB Output is correct
13 Correct 9 ms 25736 KB Output is correct
14 Correct 8 ms 25736 KB Output is correct
15 Correct 7 ms 25736 KB Output is correct
16 Correct 9 ms 25736 KB Output is correct
17 Correct 9 ms 25736 KB Output is correct
18 Correct 9 ms 25736 KB Output is correct
19 Correct 7 ms 25736 KB Output is correct
20 Correct 10 ms 25736 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5180 KB Output is correct
4 Correct 8 ms 5188 KB Output is correct
5 Correct 142 ms 12028 KB Output is correct
6 Correct 58 ms 20748 KB Output is correct
7 Correct 94 ms 20748 KB Output is correct
8 Correct 87 ms 20748 KB Output is correct
9 Correct 132 ms 20748 KB Output is correct
10 Correct 85 ms 20748 KB Output is correct
11 Correct 8 ms 20748 KB Output is correct
12 Correct 7 ms 20748 KB Output is correct
13 Correct 9 ms 20748 KB Output is correct
14 Execution timed out 1088 ms 24636 KB Time limit exceeded
15 Halted 0 ms 0 KB -