Submission #395580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
395580	2021-04-28T15:51:11 Z	arwaeystoamneg	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	522 ms	57484 KB

election_campaign

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
const int MAX = 100005, SZ = 20;
int n, m, depth[MAX];
vi adj[MAX];
vector<pair<pii, int>>queries[MAX];
ll a[MAX], dp[MAX];
template<int SZ>struct hld
{
	struct item
	{
		ll sum;
	};
	item single(ll i)
	{
		return { i };
	}
	item merge(item x, item y)
	{
		item ans;
		ans.sum = x.sum + y.sum;
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0 };
	void build(vector<item>& A, int v, int tl, int tr)
	{
		if (tl == tr)
			tree[v] = A[tl];
		else
		{
			int mid = (tl + tr) / 2;
			build(A, 2 * v + 1, tl, mid);
			build(A, 2 * v + 2, mid + 1, tr);
			tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		}
	}
	void build(vll& B)
	{
		int	n = B.size();
		height = log2(n + 1) + 1;
		A.rsz(n);
		tree.rsz((1 << height + 1) - 1);
		F0R(i, n)A[i] = single(B[i]);
		A.rsz(1 << height, neutral);
		build(A, 0, 0, (1 << height) - 1);
	}
	item query(int v, int tl, int tr, int l, int r)
	{
		if (r<tl || l>tr)return neutral;
		if (l <= tl && r >= tr)
		{
			return tree[v];
		}
		int mid = (tl + tr) / 2;
		return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	}
	ll query(int l, int r)
	{
		return query(0, 0, (1 << height) - 1, l, r).sum;
	}
	void update(int v, int tl, int tr, int pos, item val)
	{
		if (tl == tr)
		{
			tree[v] = val;
		}
		else
		{
			int mid = (tl + tr) / 2;
			if (pos <= mid)
				update(2 * v + 1, tl, mid, pos, val);
			else
				update(2 * v + 2, mid + 1, tr, pos, val);
			tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		}
	}
	void update(int pos, ll val)
	{
		update(0, 0, (1 << height) - 1, pos, single(val));
	}
	vi label, sizes, depth, heavy_child, parent, head, dist;
	vector<vi>jump;
	int get(int a, int b)
	{
		F0R(j, SZ)
		{
			if (b & (1 << j))
			{
				a = jump[a][j];
			}
		}
		return a;
	}
	int LCA(int a, int b)
	{
		if (depth[a] < depth[b])swap(a, b);
		a = get(a, depth[a] - depth[b]);
		if (a == b)return a;
		int j = SZ;
		while (j)
		{
			j--;
			int ta = jump[a][j], tb = jump[b][j];
			if (ta != tb)a = ta, b = tb;
		}
		return parent[a];
	}
	void dfs0(int i, int p)
	{
		parent[i] = p;
		sizes[i] = 1;
		trav(x, adj[i])
		{
			if (x == p)continue;
			depth[x] = depth[i] + 1;
			dfs0(x, i);
			sizes[i] += sizes[x];
		}
	}
	int cur = 0;
	void dfs1(int i, int p)
	{
		label[i] = cur++;
		if (heavy_child[i] != -1)
		{
			head[heavy_child[i]] = head[i];
			dfs1(heavy_child[i], i);
			dist[i] = 1 + dist[heavy_child[i]];
		}
		trav(x, adj[i])
		{
			if (x != heavy_child[i] && x != p)
			{
				head[x] = x;
				dfs1(x, i);
			}
		}
	}
	void init()
	{
		sizes.rsz(n);
		depth.rsz(n);
		parent.rsz(n);
		dfs0(0, -1);
		jump.rsz(n, vi(SZ));
		F0R(i, n)jump[i][0] = parent[i];
		F0R(i, SZ - 1)
		{
			F0R(j, n)jump[j][i + 1] = (jump[j][i] == -1 ? -1 : jump[jump[j][i]][i]);
		}
		heavy_child.rsz(n);
		F0R(i, n)
		{
			vpi t;
			trav(x, adj[i])if (parent[i] != x)t.pb({ sizes[x],x });
			sort(all(t), greater<pii>());
			if (sz(t))heavy_child[i] = t[0].s;
			else heavy_child[i] = -1;
		}
		label.rsz(n);
		head.rsz(n);
		dist.rsz(n);
		dfs1(0, -1);
		vll t(n);
		F0R(i, n)t[label[i]] = a[i];
		build(t);
	}
	ll solve(int x, int l)// find the sum of the values from x to l excluding l.
	{
		ll ans = 0;
		while (1)
		{
			if (x == l)return ans;
			if (head[x] == x)
			{
				ans += a[x];
				x = parent[x];
				continue;
			}
			int h = head[x];
			if (depth[h] > depth[l])
			{
				ans += query(label[h], label[x]);
				x = parent[h];
				continue;
			}
			ans += query(label[l] + 1, label[x]);
			x = l;
		}
		return ans;
	}
	ll query_path(int x, int y)
	{
		int l = LCA(x, y);
		return solve(x, l) + solve(y, l) + a[l];
	}
	void update_path(int x, int y)
	{
		a[x] = y;
		update(label[x], y);
	}
};

hld<SZ>g;
void dfs(int i, int p = -1)
{
	ll sum = 0;
	trav(x, adj[i])
	{
		if (x == p)continue;
		depth[x] = depth[i] + 1;
		dfs(x, i);
		dp[i] += dp[x];
		sum += dp[x];
	}
	trav(x, queries[i])
	{
		int l = i;
		ll val = 0;
		if (l == x.f.f)swap(x.f.f, x.f.s);
		if (l == x.f.s)
		{
			val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + x.s + sum;
		}
		else
		{
			val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + g.query_path(x.f.s, g.get(x.f.s, depth[x.f.s] - depth[l] - 1)) + x.s + sum;
		}
		dp[i] = max(dp[i], val);
	}
	trav(x, adj[i])
	{
		if (x == p)continue;
		a[i] += dp[x];
	}
	a[i] -= dp[i];
	g.update_path(i, a[i]);
}
int main() 
{
	setIO("test1");
	cin >> n;
	F0R(i, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[--x].pb(--y);
		adj[y].pb(x);
	}
	g.init();
	cin >> m;
	F0R(i, m)
	{
		int x, y, z;
		cin >> x >> y >> z;
		int l = g.LCA(--x, --y);
		queries[l].pb({ {x,y},z });
	}
	dfs(0);
	cout << dp[0] << endl;
}

Compilation message

election_campaign.cpp: In instantiation of 'void hld<SZ>::build(vll&) [with int SZ = 20; vll = std::vector<long long int>]':
election_campaign.cpp:221:3:   required from 'void hld<SZ>::init() [with int SZ = 20]'
election_campaign.cpp:305:9:   required from here
election_campaign.cpp:97:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   97 |   tree.rsz((1 << height + 1) - 1);
      |                  ~~~~~~~^~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4944 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	5 ms	5196 KB	Output is correct
5	Correct	159 ms	28960 KB	Output is correct
6	Correct	110 ms	53764 KB	Output is correct
7	Correct	155 ms	45112 KB	Output is correct
8	Correct	124 ms	29016 KB	Output is correct
9	Correct	181 ms	40380 KB	Output is correct
10	Correct	128 ms	29064 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	4 ms	5028 KB	Output is correct
3	Correct	4 ms	5420 KB	Output is correct
4	Correct	241 ms	55080 KB	Output is correct
5	Correct	238 ms	55044 KB	Output is correct
6	Correct	207 ms	55024 KB	Output is correct
7	Correct	268 ms	55096 KB	Output is correct
8	Correct	256 ms	55076 KB	Output is correct
9	Correct	200 ms	55052 KB	Output is correct
10	Correct	266 ms	55204 KB	Output is correct

Subtask #3

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	4 ms	5028 KB	Output is correct
3	Correct	4 ms	5420 KB	Output is correct
4	Correct	241 ms	55080 KB	Output is correct
5	Correct	238 ms	55044 KB	Output is correct
6	Correct	207 ms	55024 KB	Output is correct
7	Correct	268 ms	55096 KB	Output is correct
8	Correct	256 ms	55076 KB	Output is correct
9	Correct	200 ms	55052 KB	Output is correct
10	Correct	266 ms	55204 KB	Output is correct
11	Correct	26 ms	6212 KB	Output is correct
12	Correct	273 ms	55052 KB	Output is correct
13	Correct	271 ms	55104 KB	Output is correct
14	Correct	249 ms	55072 KB	Output is correct
15	Correct	248 ms	55020 KB	Output is correct
16	Correct	205 ms	55200 KB	Output is correct
17	Correct	253 ms	55092 KB	Output is correct
18	Correct	254 ms	55112 KB	Output is correct
19	Correct	208 ms	55040 KB	Output is correct
20	Correct	261 ms	55076 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	423 ms	29884 KB	Output is correct
2	Correct	201 ms	57120 KB	Output is correct
3	Correct	505 ms	47592 KB	Output is correct
4	Correct	242 ms	31744 KB	Output is correct
5	Correct	362 ms	45844 KB	Output is correct
6	Correct	212 ms	32076 KB	Output is correct
7	Correct	490 ms	45368 KB	Output is correct
8	Correct	318 ms	32064 KB	Output is correct
9	Correct	202 ms	57088 KB	Output is correct
10	Correct	522 ms	42644 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4944 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	5 ms	5196 KB	Output is correct
5	Correct	159 ms	28960 KB	Output is correct
6	Correct	110 ms	53764 KB	Output is correct
7	Correct	155 ms	45112 KB	Output is correct
8	Correct	124 ms	29016 KB	Output is correct
9	Correct	181 ms	40380 KB	Output is correct
10	Correct	128 ms	29064 KB	Output is correct
11	Correct	7 ms	5196 KB	Output is correct
12	Correct	5 ms	5452 KB	Output is correct
13	Correct	7 ms	5452 KB	Output is correct
14	Correct	4 ms	5328 KB	Output is correct
15	Correct	5 ms	5304 KB	Output is correct
16	Correct	5 ms	5328 KB	Output is correct
17	Correct	6 ms	5196 KB	Output is correct
18	Correct	5 ms	5452 KB	Output is correct
19	Correct	5 ms	5196 KB	Output is correct
20	Correct	5 ms	5432 KB	Output is correct

Subtask #6

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4944 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	5 ms	5196 KB	Output is correct
5	Correct	159 ms	28960 KB	Output is correct
6	Correct	110 ms	53764 KB	Output is correct
7	Correct	155 ms	45112 KB	Output is correct
8	Correct	124 ms	29016 KB	Output is correct
9	Correct	181 ms	40380 KB	Output is correct
10	Correct	128 ms	29064 KB	Output is correct
11	Correct	3 ms	4940 KB	Output is correct
12	Correct	4 ms	5028 KB	Output is correct
13	Correct	4 ms	5420 KB	Output is correct
14	Correct	241 ms	55080 KB	Output is correct
15	Correct	238 ms	55044 KB	Output is correct
16	Correct	207 ms	55024 KB	Output is correct
17	Correct	268 ms	55096 KB	Output is correct
18	Correct	256 ms	55076 KB	Output is correct
19	Correct	200 ms	55052 KB	Output is correct
20	Correct	266 ms	55204 KB	Output is correct
21	Correct	26 ms	6212 KB	Output is correct
22	Correct	273 ms	55052 KB	Output is correct
23	Correct	271 ms	55104 KB	Output is correct
24	Correct	249 ms	55072 KB	Output is correct
25	Correct	248 ms	55020 KB	Output is correct
26	Correct	205 ms	55200 KB	Output is correct
27	Correct	253 ms	55092 KB	Output is correct
28	Correct	254 ms	55112 KB	Output is correct
29	Correct	208 ms	55040 KB	Output is correct
30	Correct	261 ms	55076 KB	Output is correct
31	Correct	423 ms	29884 KB	Output is correct
32	Correct	201 ms	57120 KB	Output is correct
33	Correct	505 ms	47592 KB	Output is correct
34	Correct	242 ms	31744 KB	Output is correct
35	Correct	362 ms	45844 KB	Output is correct
36	Correct	212 ms	32076 KB	Output is correct
37	Correct	490 ms	45368 KB	Output is correct
38	Correct	318 ms	32064 KB	Output is correct
39	Correct	202 ms	57088 KB	Output is correct
40	Correct	522 ms	42644 KB	Output is correct
41	Correct	7 ms	5196 KB	Output is correct
42	Correct	5 ms	5452 KB	Output is correct
43	Correct	7 ms	5452 KB	Output is correct
44	Correct	4 ms	5328 KB	Output is correct
45	Correct	5 ms	5304 KB	Output is correct
46	Correct	5 ms	5328 KB	Output is correct
47	Correct	6 ms	5196 KB	Output is correct
48	Correct	5 ms	5452 KB	Output is correct
49	Correct	5 ms	5196 KB	Output is correct
50	Correct	5 ms	5432 KB	Output is correct
51	Correct	328 ms	32492 KB	Output is correct
52	Correct	249 ms	57360 KB	Output is correct
53	Correct	499 ms	43288 KB	Output is correct
54	Correct	192 ms	31804 KB	Output is correct
55	Correct	438 ms	32376 KB	Output is correct
56	Correct	247 ms	57484 KB	Output is correct
57	Correct	399 ms	44672 KB	Output is correct
58	Correct	210 ms	31880 KB	Output is correct
59	Correct	292 ms	32292 KB	Output is correct
60	Correct	247 ms	57380 KB	Output is correct
61	Correct	379 ms	45016 KB	Output is correct
62	Correct	207 ms	32668 KB	Output is correct
63	Correct	391 ms	32656 KB	Output is correct
64	Correct	254 ms	57468 KB	Output is correct
65	Correct	484 ms	45452 KB	Output is correct
66	Correct	207 ms	31776 KB	Output is correct
67	Correct	395 ms	32576 KB	Output is correct
68	Correct	244 ms	57380 KB	Output is correct
69	Correct	328 ms	41152 KB	Output is correct
70	Correct	240 ms	31820 KB	Output is correct