oj.uz

Submission #187634

# Submission time Handle Problem Language Result Execution time Memory
187634 2020-01-13T03:54:42 Z dndhk Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 29364 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 100000;
const ll INFLL = 10000;
const int MAX_K = 20;
int N, M;
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], p[MAX_N+1], up[MAX_N+1][MAX_K+1];

void dfs(int x){
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++)	up[x][i] = up[up[x][i-1]][i-1];
	for(int i : gp[x]){
		if(i==p[x])	continue;
		lv[i] = lv[x]+1;
		p[i] = x;
		dfs(i);
	}
}

int lca(int x, int y){
	for(int i=MAX_K-1; i>=0; i--){
		if(lv[up[x][i]]>=lv[y])	x = up[x][i];
		if(lv[up[y][i]]>=lv[x])	y = up[y][i];
	}
	if(x==y)	return x;
	for(int i=MAX_K-1; i>=0; i--){
		if(up[x][i]!=up[y][i])	{
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

int dist(int x, int y){
	int ret = 0;
	for(int i=MAX_K-1; i>=0; i--){
		if(lv[up[x][i]]>=lv[y])	{
			x = up[x][i];
			ret+=(1<<i);
		}
		if(lv[up[y][i]]>=lv[x])	{
			y = up[y][i];
			ret+=(1<<i);
		}
	}
	if(x==y)	return ret;
	for(int i=MAX_K-1; i>=0; i--){
		if(up[x][i]!=up[y][i])	{
			x = up[x][i];
			y = up[y][i];
			ret+=(1<<(i+1));
		}
	}
	return ret+2;
}

int upk(int x, int y){
	for(int i=MAX_K-1; i>=0; i--){
		if(y>=(1<<i)){
			x = up[x][i];
			y-=(1<<i);
		}
	}
	return x;
}

struct Q{
	int a, b, c;
};
vector<Q> query[MAX_N+1];
int dp1[MAX_N+1], dp2[MAX_N+1], dp3[MAX_N+1];


void dfs2(int x){

	for(int i : gp[x]){
		if(i==p[x])	continue;
		dfs2(i);
		dp2[x]+=dp1[i];
	}
	dp3[x] = 0;
	for(Q q : query[x]){
		int t = q.a;
		int sum = 0;
		while(t!=x){
			sum+=dp2[t]-dp1[t];
			t = p[t];
		}
		t = q.b;
		while(t!=x){
			sum+=dp2[t]-dp1[t];
			t=p[t];
		}
		dp3[x] = max(dp3[x], dp2[x]+sum+q.c);
	}
	dp1[x] = max(dp2[x], dp3[x]);
}

int main(){
	scanf("%d", &N);
	for(int i=1; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	} 
	lv[1] = 1;dfs(1);
	scanf("%d", &M);
	for(int i=1; i<=M; i++){
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		query[lca(a, b)].pb({a, b, c});
	}
	dfs2(1);
	cout<<dp1[1];
	return 0;
}

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:118:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d%d%d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5196 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 11 ms 5028 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 128 ms 19780 KB Output is correct
6 Correct 68 ms 25704 KB Output is correct
7 Correct 127 ms 23516 KB Output is correct
8 Correct 87 ms 19704 KB Output is correct
9 Correct 124 ms 22440 KB Output is correct
10 Correct 87 ms 19576 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Execution timed out 1051 ms 29184 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Execution timed out 1051 ms 29184 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 22488 KB Output is correct
2 Execution timed out 1067 ms 29364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5196 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 11 ms 5028 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 128 ms 19780 KB Output is correct
6 Correct 68 ms 25704 KB Output is correct
7 Correct 127 ms 23516 KB Output is correct
8 Correct 87 ms 19704 KB Output is correct
9 Correct 124 ms 22440 KB Output is correct
10 Correct 87 ms 19576 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 8 ms 5244 KB Output is correct
13 Correct 8 ms 5244 KB Output is correct
14 Correct 8 ms 5240 KB Output is correct
15 Correct 10 ms 5240 KB Output is correct
16 Correct 8 ms 5368 KB Output is correct
17 Correct 7 ms 5240 KB Output is correct
18 Correct 8 ms 5240 KB Output is correct
19 Correct 7 ms 5240 KB Output is correct
20 Correct 8 ms 5240 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5196 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 11 ms 5028 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 128 ms 19780 KB Output is correct
6 Correct 68 ms 25704 KB Output is correct
7 Correct 127 ms 23516 KB Output is correct
8 Correct 87 ms 19704 KB Output is correct
9 Correct 124 ms 22440 KB Output is correct
10 Correct 87 ms 19576 KB Output is correct
11 Correct 7 ms 4984 KB Output is correct
12 Correct 5 ms 5112 KB Output is correct
13 Correct 5 ms 5112 KB Output is correct
14 Execution timed out 1051 ms 29184 KB Time limit exceeded
15 Halted 0 ms 0 KB -