oj.uz

Submission #960512

# Submission time Handle Problem Language Result Execution time Memory
960512 2024-04-10T14:47:02 Z pcc Election Campaign (JOI15_election_campaign) C++17
30 / 100
 1000 ms 25776 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;
int N,Q;

vector<int> tree[mxn];
vector<pair<pii,int>> req[mxn];

namespace HLD{
	int idx[mxn],link_top[mxn],par[mxn],dep[mxn],bs[mxn],sz[mxn];
	ll bit[mxn];
	void modify(int p,ll v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	ll getval(int s,int e){
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
	int cnt = 0;
	void dfs1(int now){
		sz[now] = 1;
		for(auto nxt:tree[now]){
			if(nxt == par[now])continue;
			par[nxt] = now;
			dep[nxt] = dep[now]+1;
			dfs1(nxt);
			if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
		}
		return;
	}
	void dfs2(int now,int top){
		idx[now] = ++cnt;
		link_top[now] = top;
		if(bs[now])dfs2(bs[now],top);
		for(auto nxt:tree[now]){
			if(nxt == par[now]||nxt == bs[now])continue;
			dfs2(nxt,nxt);
		}
		return;
	}
	pll LCA(int a,int b){
		pll re = pll(0,0);
		int ta = link_top[a],tb = link_top[b];
		while(ta != tb){
			if(dep[ta]<dep[tb]){
				swap(a,b);
				swap(ta,tb);
			}
			re.sc += getval(idx[ta],idx[a]);
			a = par[ta];ta = link_top[a];
		}
		if(idx[a]>idx[b])swap(a,b);
		re.sc += getval(idx[a],idx[b]);
		re.fs = a;
		return re;
	}
}

namespace CALC{
	ll ans = 0;
	ll sum[mxn],dp[mxn];
	void dfs(int now){
		for(auto nxt:tree[now]){
			if(nxt == HLD::par[now])continue;
			dfs(nxt);
			sum[now] += dp[nxt];
		}
		dp[now] = max(dp[now],sum[now]);
		for(auto &i:req[now]){
			auto [a,b] = i.fs;
			int w = i.sc;
			ll ts = sum[now]+HLD::LCA(a,b).sc+w;
			dp[now] = max(dp[now],ts);
		}
		HLD::modify(HLD::idx[now],sum[now]-dp[now]);
	}
	void GO(){
		dfs(1);
		cout<<dp[1]<<'\n';
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	HLD::dfs1(1);
	HLD::dfs2(1,1);
	cin>>Q;
	while(Q--){
		int a,b,c;
		cin>>a>>b>>c;
		int h = HLD::LCA(a,b).fs;
		req[h].push_back(make_pair(pii(a,b),c));
	}
	CALC::GO();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 38 ms 14168 KB Output is correct
6 Correct 30 ms 21844 KB Output is correct
7 Correct 54 ms 19232 KB Output is correct
8 Correct 26 ms 13916 KB Output is correct
9 Correct 44 ms 17444 KB Output is correct
10 Correct 29 ms 13652 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 2 ms 7756 KB Output is correct
4 Correct 60 ms 25188 KB Output is correct
5 Correct 61 ms 25040 KB Output is correct
6 Correct 62 ms 25172 KB Output is correct
7 Correct 61 ms 25024 KB Output is correct
8 Correct 62 ms 25068 KB Output is correct
9 Correct 63 ms 25176 KB Output is correct
10 Correct 60 ms 25212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 2 ms 7756 KB Output is correct
4 Correct 60 ms 25188 KB Output is correct
5 Correct 61 ms 25040 KB Output is correct
6 Correct 62 ms 25172 KB Output is correct
7 Correct 61 ms 25024 KB Output is correct
8 Correct 62 ms 25068 KB Output is correct
9 Correct 63 ms 25176 KB Output is correct
10 Correct 60 ms 25212 KB Output is correct
11 Correct 7 ms 8536 KB Output is correct
12 Correct 61 ms 25512 KB Output is correct
13 Correct 66 ms 25296 KB Output is correct
14 Correct 68 ms 25364 KB Output is correct
15 Correct 66 ms 25316 KB Output is correct
16 Correct 68 ms 25776 KB Output is correct
17 Correct 67 ms 25308 KB Output is correct
18 Correct 62 ms 25348 KB Output is correct
19 Correct 64 ms 25348 KB Output is correct
20 Correct 64 ms 25424 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16976 KB Output is correct
2 Correct 66 ms 25076 KB Output is correct
3 Execution timed out 1047 ms 17320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 38 ms 14168 KB Output is correct
6 Correct 30 ms 21844 KB Output is correct
7 Correct 54 ms 19232 KB Output is correct
8 Correct 26 ms 13916 KB Output is correct
9 Correct 44 ms 17444 KB Output is correct
10 Correct 29 ms 13652 KB Output is correct
11 Correct 3 ms 7512 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 3 ms 7772 KB Output is correct
14 Correct 2 ms 7772 KB Output is correct
15 Correct 3 ms 7512 KB Output is correct
16 Correct 2 ms 7772 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 3 ms 7772 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7672 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 38 ms 14168 KB Output is correct
6 Correct 30 ms 21844 KB Output is correct
7 Correct 54 ms 19232 KB Output is correct
8 Correct 26 ms 13916 KB Output is correct
9 Correct 44 ms 17444 KB Output is correct
10 Correct 29 ms 13652 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 4 ms 7516 KB Output is correct
13 Correct 2 ms 7756 KB Output is correct
14 Correct 60 ms 25188 KB Output is correct
15 Correct 61 ms 25040 KB Output is correct
16 Correct 62 ms 25172 KB Output is correct
17 Correct 61 ms 25024 KB Output is correct
18 Correct 62 ms 25068 KB Output is correct
19 Correct 63 ms 25176 KB Output is correct
20 Correct 60 ms 25212 KB Output is correct
21 Correct 7 ms 8536 KB Output is correct
22 Correct 61 ms 25512 KB Output is correct
23 Correct 66 ms 25296 KB Output is correct
24 Correct 68 ms 25364 KB Output is correct
25 Correct 66 ms 25316 KB Output is correct
26 Correct 68 ms 25776 KB Output is correct
27 Correct 67 ms 25308 KB Output is correct
28 Correct 62 ms 25348 KB Output is correct
29 Correct 64 ms 25348 KB Output is correct
30 Correct 64 ms 25424 KB Output is correct
31 Correct 198 ms 16976 KB Output is correct
32 Correct 66 ms 25076 KB Output is correct
33 Execution timed out 1047 ms 17320 KB Time limit exceeded
34 Halted 0 ms 0 KB -