Submission #921603

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921603	2024-02-04T07:51:29 Z	firewater	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	1000 ms	27092 KB

election_campaign

#include<bits/stdc++.h>
#define fs first
#define sn second
#define mp make_pair
#define N 100100
#define ll long long
using namespace std;
ll n,m,ans,x,y,z,w,tot,h[N],f[N],sz[N],hs[N],top[N],fa[N],dep[N],dfn[N],low[N],v[N];
vector<pair<pair<ll,ll>,ll> >d[N];
struct rec
{
	ll to,nx;
}e[N<<1];
void addl(ll x,ll y)
{
	e[++tot].to=y;
	e[tot].nx=h[x];
	h[x]=tot;
	return;
}
struct Tree
{
	#define ls x*2
	#define rs x*2+1
	ll s[N<<2];
	void push_up(ll x)
	{
		s[x]=s[ls]+s[rs];
		return;
	}
	void change(ll x,ll l,ll r,ll y,ll z)
	{
		if(l>r||y<l||y>r)s[-1]=1;
		if(l==r){
			s[x]+=z;
			return;
		}
		ll mid=l+r>>1;
		if(y<=mid)change(ls,l,mid,y,z);
		else change(rs,mid+1,r,y,z);
		push_up(x);
		return;
	}
	ll ask(ll x,ll L,ll R,ll l,ll r)
	{
		if(L>R||l>r||l<L||r>R)s[-1]=1;
		if(L==R)return s[x];
		ll mid=L+R>>1;
		if(r<=mid)return ask(ls,L,mid,l,r);
		else if(l>mid)return ask(rs,mid+1,R,l,r);
		else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r);
	}
}T;
void dfs(ll x)
{
	sz[x]=1;
	for(ll i=h[x];i;i=e[i].nx){
		ll y=e[i].to;
		if(y==fa[x])continue;
		fa[y]=x;
		dep[y]=dep[x]+1;
		dfs(y);
		sz[x]+=sz[y];
		if(sz[y]>sz[hs[x]])hs[x]=y;
	}
	return;
}
void dfs1(ll x,ll anc)
{
	dfn[x]=++w;
	top[x]=anc;
	if(hs[x])dfs1(hs[x],anc);
	for(ll i=h[x];i;i=e[i].nx){
		ll y=e[i].to;
		if(y==fa[x]||y==hs[x])continue;
		dfs1(y,y);
	}
	low[x]=w;
	return;
}
ll lca(ll x,ll y)
{
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return (dep[x]<dep[y]?x:y);
}
ll ask(ll x,ll y)
{
	ll sum=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(hs[x])sum+=f[hs[x]];
		sum+=T.ask(1,1,n,dfn[top[x]],dfn[x])-f[top[x]];
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	if(hs[y])sum+=f[hs[y]];
	sum+=T.ask(1,1,n,dfn[x],dfn[y]);
	return sum;
}
bool cmp(ll x,ll y)
{
	return dep[x]>dep[y];
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<n;++i){
		scanf("%lld%lld",&x,&y);
		addl(x,y);
		addl(y,x);
	}
	fa[1]=1;
	dep[1]=1;
	dfs(1);
	dfs1(1,1);
	scanf("%lld",&m);
	for(ll i=1;i<=m;++i){
		scanf("%lld%lld%lld",&x,&y,&z);
		ll u=lca(x,y);
		d[u].push_back(mp(mp(x,y),z));
	}
	for(ll i=1;i<=n;++i)
		v[i]=i;
	sort(v+1,v+1+n,cmp);
	for(ll i=1;i<=n;++i){
		x=v[i];
		f[x]=ask(x,x);
		for(ll j=0;j<d[x].size();++j){
			f[x]=max(f[x],ask(d[x][j].fs.fs,d[x][j].fs.sn)+d[x][j].sn);
		}
		ans=max(ans,f[x]);
		if(x!=1&&x==top[x])T.change(1,1,n,dfn[fa[x]],f[x]);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message

election_campaign.cpp: In member function 'void Tree::change(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   ll mid=l+r>>1;
      |          ~^~
election_campaign.cpp: In member function 'long long int Tree::ask(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   ll mid=L+R>>1;
      |          ~^~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:131:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(ll j=0;j<d[x].size();++j){
      |              ~^~~~~~~~~~~~
election_campaign.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  scanf("%lld",&m);
      |  ~~~~~^~~~~~~~~~~
election_campaign.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%lld%lld%lld",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp: In member function 'void Tree::change(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:33:24: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   33 |   if(l>r||y<l||y>r)s[-1]=1;
      |                    ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp: In member function 'long long int Tree::ask(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp: In function 'long long int ask(long long int, long long int)':
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^
election_campaign.cpp:46:29: warning: array subscript -1 is below array bounds of 'long long int [400400]' [-Warray-bounds]
   46 |   if(L>R||l>r||l<L||r>R)s[-1]=1;
      |                         ~~~~^
election_campaign.cpp:25:5: note: while referencing 'Tree::s'
   25 |  ll s[N<<2];
      |     ^
election_campaign.cpp:53:2: note: defined here 'T'
   53 | }T;
      |  ^

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	3 ms	12636 KB	Output is correct
5	Correct	47 ms	17852 KB	Output is correct
6	Correct	29 ms	21844 KB	Output is correct
7	Correct	51 ms	21076 KB	Output is correct
8	Correct	43 ms	15820 KB	Output is correct
9	Correct	54 ms	20044 KB	Output is correct
10	Correct	42 ms	15840 KB	Output is correct

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12632 KB	Output is correct
3	Correct	3 ms	12636 KB	Output is correct
4	Execution timed out	1044 ms	26928 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #3

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12632 KB	Output is correct
3	Correct	3 ms	12636 KB	Output is correct
4	Execution timed out	1044 ms	26928 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	22016 KB	Output is correct
2	Execution timed out	1002 ms	27092 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	3 ms	12636 KB	Output is correct
5	Correct	47 ms	17852 KB	Output is correct
6	Correct	29 ms	21844 KB	Output is correct
7	Correct	51 ms	21076 KB	Output is correct
8	Correct	43 ms	15820 KB	Output is correct
9	Correct	54 ms	20044 KB	Output is correct
10	Correct	42 ms	15840 KB	Output is correct
11	Correct	3 ms	12632 KB	Output is correct
12	Correct	4 ms	12636 KB	Output is correct
13	Correct	3 ms	12636 KB	Output is correct
14	Correct	3 ms	12636 KB	Output is correct
15	Correct	3 ms	12636 KB	Output is correct
16	Correct	3 ms	12636 KB	Output is correct
17	Correct	3 ms	12636 KB	Output is correct
18	Correct	4 ms	12636 KB	Output is correct
19	Correct	3 ms	12636 KB	Output is correct
20	Correct	4 ms	12636 KB	Output is correct

Subtask #6

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	12632 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	3 ms	12636 KB	Output is correct
5	Correct	47 ms	17852 KB	Output is correct
6	Correct	29 ms	21844 KB	Output is correct
7	Correct	51 ms	21076 KB	Output is correct
8	Correct	43 ms	15820 KB	Output is correct
9	Correct	54 ms	20044 KB	Output is correct
10	Correct	42 ms	15840 KB	Output is correct
11	Correct	2 ms	12632 KB	Output is correct
12	Correct	2 ms	12632 KB	Output is correct
13	Correct	3 ms	12636 KB	Output is correct
14	Execution timed out	1044 ms	26928 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-