oj.uz

Submission #366543

# Submission time Handle Problem Language Result Execution time Memory
366543 2021-02-14T12:00:41 Z Rainbowbunny Election Campaign (JOI15_election_campaign) C++17
0 / 100
 341 ms 21992 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>

int n, timer;
int tin[100005], tout[100005], up[20][100005];
std::vector <int> Adj[100005];

int m;
int A[100005], B[100005], C[100005];
int dp[100005];
std::vector <int> Query[100005];

int BIT[100005];

void Add(int id, int value)
{
	for(id; id <= n; id += id & -id)
	{
		BIT[id] += value; 
	}
}

int Get(int id)
{
	int ans = 0;
	for(id; id > 0; id -= id & -id)
	{
		ans += BIT[id];
	}
	return ans;
}

void DFS(int node, int p)
{
	timer++;
	tin[node] = timer;
	up[0][node] = p;
	for(int i = 1; i <= 19; i++)
	{
		up[i][node] = up[i - 1][up[i - 1][node]];
	}
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		DFS(x, node);
	}
	tout[node] = timer;
}

int Isparent(int u, int v)
{
	return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int LCA(int u, int v)
{
	if(Isparent(u, v))
	{
		return u;
	}
	for(int i = 19; i >= 0; i--)
	{
		if(!Isparent(up[i][u], v))
		{
			u = up[i][u];
		}
	}
	return up[0][u];
}

int Subtree(int u, int v)
{
	assert(Isparent(u, v));
	for(int i = 19; i >= 0; i--)
	{
		if(!Isparent(up[i][v], u))
		{
			v = up[i][v];
		}
	}
	return v;
}

void Caldp(int node, int p)
{
	int sumdp = 0;
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		Caldp(x, node);
		sumdp += dp[x];
	}
	for(auto x : Query[node])
	{
		if(A[x] == B[x])
		{
			dp[node] = std::max(dp[node], sumdp + C[x]);
		}
		else if(A[x] == node)
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(A[x], B[x])] + Get(tin[B[x]]) + C[x]);	
		}
		else if(B[x] == node)
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(B[x], A[x])] + Get(tin[A[x]]) + C[x]);
		}
		else
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(node, A[x])] - dp[Subtree(node, B[x])] + Get(tin[A[x]]) + Get(tin[B[x]]) + C[x]);
		}
	}
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		Add(tin[x], sumdp - dp[x]);
		Add(tout[x] + 1, dp[x] - sumdp);
	}
	Add(tin[node], sumdp);
	Add(tin[node] + 1, -sumdp);
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n;
	for(int i = 1; i < n; i++)
	{
		int u, v;
		std::cin >> u >> v;
		Adj[u].push_back(v);
		Adj[v].push_back(u);
	}
	DFS(1, 1);
	std::cin >> m;
	for(int i = 1; i <= m; i++)
	{
		std::cin >> A[i] >> B[i] >> C[i];
		Query[LCA(A[i], B[i])].push_back(i);
	}
	Caldp(1, 1);
	std::cout << *std::max_element(dp + 1, dp + n + 1);
}

Compilation message

election_campaign.cpp: In function 'void Add(int, int)':
election_campaign.cpp:29:6: warning: statement has no effect [-Wunused-value]
   29 |  for(id; id <= n; id += id & -id)
      |      ^~
election_campaign.cpp: In function 'int Get(int)':
election_campaign.cpp:38:6: warning: statement has no effect [-Wunused-value]
   38 |  for(id; id > 0; id -= id & -id)
      |      ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Incorrect 3 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Incorrect 3 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Incorrect 3 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Incorrect 3 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Incorrect 3 ms 5100 KB Output isn't correct
4 Halted 0 ms 0 KB -