oj.uz

Submission #70899

# Submission time Handle Problem Language Result Execution time Memory
70899 2018-08-23T16:13:09 Z zadrga Election Campaign (JOI15_election_campaign) C++14
10 / 100
 355 ms 34048 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111
#define logn 20

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

vector<int> adj[maxn];
vector<vector<int> > query[maxn];

int in[maxn], out[maxn], dep[maxn];
int par[maxn][logn];
ll dp[maxn];
int cnt;

struct BIT{
	ll bit[maxn];

	int query(int x){
		ll ret = 0;
		while(x){
			ret += bit[x];
			x -= (x & -x);
		}
		return ret;
	}

	void update(int x, ll val){
		while(x < maxn){
			bit[x] += val;
			x += (x & -x);
		}
	}
} bit;

void DFS(int x, int p){
	in[x] = ++cnt;
	par[x][0] = p;

	for(int v : adj[x]){
		if(v == p)
			continue;

		dep[v] = dep[x] + 1;
		DFS(v, x);
	}

	out[x] = cnt;
}

int LCA(int a, int b){
	if(dep[a] > dep[b])
		swap(a, b);

	int raz = dep[b] - dep[a];
	for(int i = 0; i < logn; i++){
		if((raz >> i) & 1)
			b = par[b][i]; 
	}

	if(a == b)
		return a;

	for(int i = logn - 1; i >= 0; i--){
		if(par[a][i] != par[b][i]){
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

void solve(int x, int p){
	dp[x] = 0;
	ll sum = 0;
	for(int v : adj[x]){
		if(v == p)
			continue;

		solve(v, x);
		sum += dp[v];
		dp[x] = max(dp[x], dp[v]);
	}

	for(vector<int> a : query[x]){
		int u = a[0], v = a[1], cost = a[2];
		ll cur = 0;
		cur += bit.query(in[u]);
		cur += bit.query(in[v]);
		dp[x] = max(dp[x], sum + cur + cost);
	}

	ll cur = sum - dp[x];
	bit.update(in[x], cur);
	bit.update(out[x] + 1, -cur);
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n - 1; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].pb(b);
		adj[b].pb(a);
	}

	DFS(1, 0);

	for(int j = 1; j < logn; j++)
		for(int i = 1; i <= n; i++)
			par[i][j] = par[par[i][j - 1]][j - 1];

	int m;
	scanf("%d", &m);
	for(int i = 0; i < m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		int lca = LCA(a, b);
		query[lca].pb({a, b, c});
	}

	solve(1, 0);

	printf("%lld\n", dp[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:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5152 KB Output is correct
4 Incorrect 7 ms 5360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5420 KB Output is correct
2 Correct 6 ms 5420 KB Output is correct
3 Correct 9 ms 5596 KB Output is correct
4 Correct 247 ms 33896 KB Output is correct
5 Correct 260 ms 33896 KB Output is correct
6 Correct 263 ms 33896 KB Output is correct
7 Correct 259 ms 33920 KB Output is correct
8 Correct 264 ms 34048 KB Output is correct
9 Correct 229 ms 34048 KB Output is correct
10 Correct 252 ms 34048 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5420 KB Output is correct
2 Correct 6 ms 5420 KB Output is correct
3 Correct 9 ms 5596 KB Output is correct
4 Correct 247 ms 33896 KB Output is correct
5 Correct 260 ms 33896 KB Output is correct
6 Correct 263 ms 33896 KB Output is correct
7 Correct 259 ms 33920 KB Output is correct
8 Correct 264 ms 34048 KB Output is correct
9 Correct 229 ms 34048 KB Output is correct
10 Correct 252 ms 34048 KB Output is correct
11 Correct 27 ms 34048 KB Output is correct
12 Correct 312 ms 34048 KB Output is correct
13 Correct 240 ms 34048 KB Output is correct
14 Correct 206 ms 34048 KB Output is correct
15 Correct 278 ms 34048 KB Output is correct
16 Correct 292 ms 34048 KB Output is correct
17 Correct 355 ms 34048 KB Output is correct
18 Correct 261 ms 34048 KB Output is correct
19 Correct 248 ms 34048 KB Output is correct
20 Correct 291 ms 34048 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 290 ms 34048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5152 KB Output is correct
4 Incorrect 7 ms 5360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5152 KB Output is correct
4 Incorrect 7 ms 5360 KB Output isn't correct
5 Halted 0 ms 0 KB -