Submission #342549

#	Time	Username	Problem	Language	Result	Execution time	Memory
342549		Nursik	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	242 ms	77292 KiB

election_campaign

#include <bits/stdc++.h>
          
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end() 
#define mp make_pair 
using namespace std;        
 
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2; 
const ll pe2 = 570210983;
const ld eps = 1e-6; 
 
 
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
	#ifdef NURS
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif	
} 

int n, m, timer;
int tin[N], tout[N], up[20][N];
ll dp[N], dp2[N], l[N], r[N], w[N];
vector<int> g[N], g2[N];
struct fenw
{
	ll f[N * 4];
	void upd(int pos, int val)
	{
		for (int i = pos; i <= N; i = (i | (i + 1)))
			f[i] += val;
	}
	ll sum(int pos)
	{
		ll res = 0;
		for (int i = pos; i >= 1; i = (i & (i + 1)) - 1)
			res += f[i];
		return res;
	}
	ll get(int l, int r)
	{
		return sum(r) - sum(l - 1);
	}
};
fenw tr, tr2;
void dfs(int v, int p)
{
	tin[v] = ++timer;
	up[0][v] = p;
	for (int i = 1; i <= 20; i++)
		up[i][v] = up[i - 1][up[i - 1][v]];

	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)
			continue;
		dfs(to, v);
	}
	tout[v] = ++timer;
}
bool upper(int a, int b)
{
	return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
int lca(int a, int b)
{
	if (upper(a, b))
		return a;
	if (upper(b, a))
		return b;
	for (int i = 20; i >= 0; i--)
	{
		if (up[i][a] && !upper(up[i][a], b))
			a = up[i][a];
	}
	return up[0][a];
}    
void dfs2(int v, int p)
{
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)
			continue;
		dfs2(to, v);
	   	dp[v] += dp2[to];
	}
	dp2[v] = dp[v];
	for (int i = 0; i < g2[v].size(); i++)
	{
		int pos = g2[v][i];
		int a = l[pos], b = r[pos];
		dp2[v] = max(dp2[v] , dp[v] + tr.get(tin[v], tin[a]) + tr.get(tin[v], tin[b]) 
					 				- tr2.get(tin[v], tin[a]) - tr2.get(tin[v], tin[b]) + w[pos]); 
	}
	tr.upd(tin[v], dp[v]);
	tr.upd(tout[v], -dp[v]);
	tr2.upd(tin[v], dp2[v]);
	tr2.upd(tout[v], -dp2[v]);
}
int main()
{
	data();
	ios_base::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].pb(v), g[v].pb(u);
	}
	dfs(1, 0);
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> l[i] >> r[i] >> w[i];
		int lc = lca(l[i], r[i]);
		g2[lc].pb(i);
	}
	dfs2(1, 0);
	cout << dp2[1];
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i = 0; i < g[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs2(int, int)':
election_campaign.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for (int i = 0; i < g[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~
election_campaign.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 0; i < g2[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:64:12: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   64 |   up[i][v] = up[i - 1][up[i - 1][v]];
      |   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:63:20: note: within this loop
   63 |  for (int i = 1; i <= 20; i++)
      |                  ~~^~~~~

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40