Submission #484387

#	Time	Username	Problem	Language	Result	Execution time	Memory
484387		MilosMilutinovic	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	184 ms	33860 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
int n,m,dp[N][2],dep[N],a[N],b[N],c[N];
VI g[N],qs[N];
#define LOGN 24
int up[N][LOGN];
void dfs(int x,int f) {
	up[x][0]=f;
	dep[x]=dep[f]+1;
	for (auto u:g[x]) if (u!=f) dfs(u,x);
}
int lca(int x,int y) {
	if (dep[x]<dep[y]) swap(x,y);
	per(i,0,LOGN) if (dep[up[x][i]]>=dep[y]) x=up[x][i];
	if (x==y) return x;
	per(i,0,LOGN) if (up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
	if (x!=y) x=up[x][0];
	return x;
}
int lift(int x,int k) {
	rep(i,0,LOGN) if ((k>>i)&1) x=up[x][i];
	return x;
}
int dist(int x,int y) {
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
//dp[u][0] -> max sum without u
//dp[u][1] ->         with u
void gao(int x,int f) {
	for (auto u:g[x]) if (u!=f) gao(u,x),dp[x][0]+=max(dp[u][0],dp[u][1]);
	for (auto p:qs[x]) {
		if (a[p]==x&&b[p]==x) dp[x][1]=max(dp[x][1],dp[x][0]+c[p]);
		else {
			if (a[p]==x) {
				int pb=lift(b[p],dist(b[p],x)-1);
				dp[x][1]=max(dp[x][1],dp[b[p]][0]+dp[x][0]-max(dp[pb][0],dp[pb][1])+c[p]);
			} else {
				if (b[p]==x) {
					int pa=lift(a[p],dist(a[p],x)-1);
					dp[x][1]=max(dp[x][1],dp[a[p]][0]+dp[x][0]-max(dp[pa][0],dp[pa][1])+c[p]);
				} else {
					int pa=lift(a[p],dist(a[p],x)-1);
					int pb=lift(b[p],dist(b[p],x)-1);
					dp[x][1]=max(dp[x][1],dp[a[p]][0]+dp[b[p]][0]+dp[x][0]-max(dp[pa][0],dp[pa][1])-max(dp[pb][0],dp[pb][1])+c[p]);
				}
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].pb(y);
		g[y].pb(x);
	}
	scanf("%d",&m);
	dfs(1,0);
	rep(j,1,LOGN) rep(i,1,n+1) up[i][j]=up[up[i][j-1]][j-1];
	rep(i,1,m+1) {
		scanf("%d%d%d",a+i,b+i,c+i);
		qs[lca(a[i],b[i])].pb(i);
	}
	gao(1,0);
	printf("%lld",max(dp[1][0],dp[1][1]));
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:86:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   86 |  printf("%lld",max(dp[1][0],dp[1][1]));
      |          ~~~^  ~~~~~~~~~~~~~~~~~~~~~~
      |             |     |
      |             |     int
      |             long long int
      |          %d
election_campaign.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
election_campaign.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d",&m);
      |  ~~~~~^~~~~~~~~
election_campaign.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d%d",a+i,b+i,c+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