답안 #68671 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68671	2018-08-17T22:25:43 Z	IvanC	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	425 ms	33228 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	5 ms	5112 KB	Output is correct
3	Correct	7 ms	5152 KB	Output is correct
4	Correct	7 ms	5356 KB	Output is correct
5	Correct	148 ms	19436 KB	Output is correct
6	Correct	89 ms	27136 KB	Output is correct
7	Correct	128 ms	27136 KB	Output is correct
8	Correct	106 ms	27136 KB	Output is correct
9	Correct	154 ms	27136 KB	Output is correct
10	Correct	116 ms	27136 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	27136 KB	Output is correct
2	Correct	6 ms	27136 KB	Output is correct
3	Correct	7 ms	27136 KB	Output is correct
4	Correct	227 ms	29436 KB	Output is correct
5	Correct	228 ms	31956 KB	Output is correct
6	Correct	214 ms	33172 KB	Output is correct
7	Correct	211 ms	33172 KB	Output is correct
8	Correct	234 ms	33172 KB	Output is correct
9	Correct	203 ms	33172 KB	Output is correct
10	Correct	242 ms	33172 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	27136 KB	Output is correct
2	Correct	6 ms	27136 KB	Output is correct
3	Correct	7 ms	27136 KB	Output is correct
4	Correct	227 ms	29436 KB	Output is correct
5	Correct	228 ms	31956 KB	Output is correct
6	Correct	214 ms	33172 KB	Output is correct
7	Correct	211 ms	33172 KB	Output is correct
8	Correct	234 ms	33172 KB	Output is correct
9	Correct	203 ms	33172 KB	Output is correct
10	Correct	242 ms	33172 KB	Output is correct
11	Correct	20 ms	33172 KB	Output is correct
12	Correct	282 ms	33172 KB	Output is correct
13	Correct	213 ms	33172 KB	Output is correct
14	Correct	228 ms	33172 KB	Output is correct
15	Correct	287 ms	33172 KB	Output is correct
16	Correct	223 ms	33172 KB	Output is correct
17	Correct	263 ms	33228 KB	Output is correct
18	Correct	269 ms	33228 KB	Output is correct
19	Correct	230 ms	33228 KB	Output is correct
20	Correct	275 ms	33228 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	306 ms	33228 KB	Output is correct
2	Correct	210 ms	33228 KB	Output is correct
3	Correct	378 ms	33228 KB	Output is correct
4	Correct	182 ms	33228 KB	Output is correct
5	Correct	322 ms	33228 KB	Output is correct
6	Correct	211 ms	33228 KB	Output is correct
7	Correct	400 ms	33228 KB	Output is correct
8	Correct	242 ms	33228 KB	Output is correct
9	Correct	196 ms	33228 KB	Output is correct
10	Correct	329 ms	33228 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	5 ms	5112 KB	Output is correct
3	Correct	7 ms	5152 KB	Output is correct
4	Correct	7 ms	5356 KB	Output is correct
5	Correct	148 ms	19436 KB	Output is correct
6	Correct	89 ms	27136 KB	Output is correct
7	Correct	128 ms	27136 KB	Output is correct
8	Correct	106 ms	27136 KB	Output is correct
9	Correct	154 ms	27136 KB	Output is correct
10	Correct	116 ms	27136 KB	Output is correct
11	Correct	7 ms	33228 KB	Output is correct
12	Correct	9 ms	33228 KB	Output is correct
13	Correct	7 ms	33228 KB	Output is correct
14	Correct	10 ms	33228 KB	Output is correct
15	Correct	9 ms	33228 KB	Output is correct
16	Correct	10 ms	33228 KB	Output is correct
17	Correct	8 ms	33228 KB	Output is correct
18	Correct	10 ms	33228 KB	Output is correct
19	Correct	10 ms	33228 KB	Output is correct
20	Correct	7 ms	33228 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	5 ms	5112 KB	Output is correct
3	Correct	7 ms	5152 KB	Output is correct
4	Correct	7 ms	5356 KB	Output is correct
5	Correct	148 ms	19436 KB	Output is correct
6	Correct	89 ms	27136 KB	Output is correct
7	Correct	128 ms	27136 KB	Output is correct
8	Correct	106 ms	27136 KB	Output is correct
9	Correct	154 ms	27136 KB	Output is correct
10	Correct	116 ms	27136 KB	Output is correct
11	Correct	8 ms	27136 KB	Output is correct
12	Correct	6 ms	27136 KB	Output is correct
13	Correct	7 ms	27136 KB	Output is correct
14	Correct	227 ms	29436 KB	Output is correct
15	Correct	228 ms	31956 KB	Output is correct
16	Correct	214 ms	33172 KB	Output is correct
17	Correct	211 ms	33172 KB	Output is correct
18	Correct	234 ms	33172 KB	Output is correct
19	Correct	203 ms	33172 KB	Output is correct
20	Correct	242 ms	33172 KB	Output is correct
21	Correct	20 ms	33172 KB	Output is correct
22	Correct	282 ms	33172 KB	Output is correct
23	Correct	213 ms	33172 KB	Output is correct
24	Correct	228 ms	33172 KB	Output is correct
25	Correct	287 ms	33172 KB	Output is correct
26	Correct	223 ms	33172 KB	Output is correct
27	Correct	263 ms	33228 KB	Output is correct
28	Correct	269 ms	33228 KB	Output is correct
29	Correct	230 ms	33228 KB	Output is correct
30	Correct	275 ms	33228 KB	Output is correct
31	Correct	306 ms	33228 KB	Output is correct
32	Correct	210 ms	33228 KB	Output is correct
33	Correct	378 ms	33228 KB	Output is correct
34	Correct	182 ms	33228 KB	Output is correct
35	Correct	322 ms	33228 KB	Output is correct
36	Correct	211 ms	33228 KB	Output is correct
37	Correct	400 ms	33228 KB	Output is correct
38	Correct	242 ms	33228 KB	Output is correct
39	Correct	196 ms	33228 KB	Output is correct
40	Correct	329 ms	33228 KB	Output is correct
41	Correct	7 ms	33228 KB	Output is correct
42	Correct	9 ms	33228 KB	Output is correct
43	Correct	7 ms	33228 KB	Output is correct
44	Correct	10 ms	33228 KB	Output is correct
45	Correct	9 ms	33228 KB	Output is correct
46	Correct	10 ms	33228 KB	Output is correct
47	Correct	8 ms	33228 KB	Output is correct
48	Correct	10 ms	33228 KB	Output is correct
49	Correct	10 ms	33228 KB	Output is correct
50	Correct	7 ms	33228 KB	Output is correct
51	Correct	266 ms	33228 KB	Output is correct
52	Correct	255 ms	33228 KB	Output is correct
53	Correct	425 ms	33228 KB	Output is correct
54	Correct	188 ms	33228 KB	Output is correct
55	Correct	225 ms	33228 KB	Output is correct
56	Correct	249 ms	33228 KB	Output is correct
57	Correct	336 ms	33228 KB	Output is correct
58	Correct	217 ms	33228 KB	Output is correct
59	Correct	254 ms	33228 KB	Output is correct
60	Correct	246 ms	33228 KB	Output is correct
61	Correct	319 ms	33228 KB	Output is correct
62	Correct	172 ms	33228 KB	Output is correct
63	Correct	245 ms	33228 KB	Output is correct
64	Correct	215 ms	33228 KB	Output is correct
65	Correct	328 ms	33228 KB	Output is correct
66	Correct	181 ms	33228 KB	Output is correct
67	Correct	238 ms	33228 KB	Output is correct
68	Correct	223 ms	33228 KB	Output is correct
69	Correct	301 ms	33228 KB	Output is correct
70	Correct	220 ms	33228 KB	Output is correct

답안 #68671

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0