Submission #154280

#	Time	Username	Problem	Language	Result	Execution time	Memory
154280		ryansee	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	752 ms	112608 KiB

election_campaign

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph emplace
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n,m;
vector<int>v[MAXN];
struct lca_{
	int st[MAXN], en[MAXN], co, p[MAXN][21], depth[MAXN];
	lca_() {
		mmst(st,0); mmst(en,0); co =0 ; mmst(p,0); mmst(depth,0);
	}
	void dfs(ll x, ll par) {
		p[x][0] = par;
		st[x]=co++;
		for(auto i : v[x]) if(i!=par) {
			depth[i]=depth[x]+1;dfs(i,x);
		}
		en[x]=co;
	}
	void main() {
		co=0;
		dfs(1,1);
		t2k();
	}
	void t2k() { for(ll j=1;j<21;j++) for(ll i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1]; }
	ll lca(ll x, ll y) {
		if(isp(x,y)) return x;
		if(isp(y,x)) return y;
		for(ll i=20;i>=0;i--) {
			if(!isp(p[x][i],y)) x=p[x][i];
		}
		return p[x][0];
	}
	bool isp(ll a, ll b) { return st[a]<=st[b]&&en[a]>=en[b]; }
	ll find2k(ll x, ll k) {
		for(ll i=20;i>=0;i--) {
			if(k>=(1ll<<i)) {
				k -= (1ll<<i);
				x=p[x][i];
			}
		}
		assert(k==0);
		return x;
	}
} lca;
spi Q[MAXN];
vector<pair<ll,bool>>at[MAXN];
set<ll>*s[MAXN];
ll dp[MAXN],sumy[MAXN];
struct fen {
	ll fw[MAXN]={0};
	fen() {mmst(fw,0); }
	void update(ll x, ll nv) { for(; x<=n;x+=x&(-x)) fw[x]+=nv;}
	ll sum(ll x) {ll res=0;for(;x;x-=x&(-x)) res+=fw[x];return res;}
	ll sum(ll a,ll b){return sum(b)-sum(a-1);} 
}fen;
struct hld_ {
	int st[MAXN],p[MAXN],depth[MAXN],head[MAXN],heavy[MAXN],co=0;
	hld_(){ FOR(i,0,MAXN)st[i]=p[i]=depth[i]=head[i]=0,heavy[i]=-1; }
	ll dfs(ll x, ll p){
		ll sz=1;
		ll mx_sz=0; 
		for(auto i:v[x])if(i!=p){
			depth[i]=depth[x]+1;
			ll c_sz=dfs(i,x);
			sz+=c_sz;
			if(c_sz>mx_sz){mx_sz=c_sz;heavy[x]=i;}
		}
		return sz;
	}
	void main(){
		dfs(1,1);
		co=1;hld(1,1,1);
		return;
	}
	void hld(ll x, ll h, ll par){
		p[x]=par;
		head[x]=h;
		st[x]=co++;
		if(heavy[x]!=-1)
			hld(heavy[x],h,x);
		for(auto i:v[x])if(i!=par&&i!=heavy[x]){
			hld(i,i,x);
		}
		return;
	}
	ll query(ll a, ll b){
		ll ans=0;
		for(;head[a]!=head[b];a=p[head[a]]){
			if(depth[head[a]]<depth[head[b]])swap(a,b);
			ans+=fen.sum(st[head[a]],st[a]);
		}
		if(depth[a]>depth[b])swap(a,b);
		return ans+fen.sum(st[a],st[b]);
	}
	void update(ll x, ll nv) { assert(1<=st[x]&&st[x]<=n); fen.update(st[x], nv); }
} hld;
void up(ll &x, ll y) { x=max(x,y); }
void dfs(ll x, ll p) {
	ll sum = 0;
	for(auto i : v[x]) if(i!=p) {
		dfs(i,x); sum+=dp[i];
	}
	sumy[x]=dp[x]=sum;
	s[x] = new set<ll>; ll poi=-1;
	for(auto i:v[x])if(i!=p){
		if(s[i]->size()>s[x]->size())s[x]=s[i],poi=i;
	}
	for(auto i:v[x])if(i!=p&&i!=poi){
		for(auto j:*s[i])s[x]->ins(j);
	}
	/* handle answer part */
	for(auto i:at[x]) {
		if(i.s) {
			ll ind = i.f;
			assert(s[x]->count(ind));
			ll a=Q[ind].s.f,b=Q[ind].s.s,c=Q[ind].f;
			if(a==x||b==x) {
				if(b==x) swap(a,b);
				ll be = lca.find2k(b,lca.depth[b]-lca.depth[x]-1);
				assert(~be);
				// dp[x] = max(dp[x], sum+c+sumy[b]-dp[be]);
				ll val = ((hld.depth[be] <= hld.depth[hld.p[b]]) ? hld.query(hld.p[b],be)+sum-dp[b]+sumy[b] : sum-dp[be]+sumy[b])+c;
				up(dp[x],val);
			} else { // assert(0);
				ll bea=-1,beb=-1; bea = lca.find2k(a, lca.depth[a]-lca.depth[x]-1); beb = lca.find2k(b, lca.depth[b]-lca.depth[x]-1);
				// for(auto i:v[x])if(i!=p){if(lca.isp(i,a))bea=i;}
				// for(auto i:v[x])if(i!=p){if(lca.isp(i,b))beb=i;}
				assert((~bea)&&(~beb));
				// cerr << "Query: " << x << ' ' << a << ' ' << bea << ' ' << b << ' ' << beb << ' ';
				// dp[x]=max(dp[x],sum+c+sumy[a]+sumy[b]-dp[bea]-dp[beb]);
				ll val = 0;
				ll separate = sum - dp[bea] - dp[beb];
				ll b_side = ((hld.depth[beb] <= hld.depth[hld.p[b]]) ? (hld.query(beb, hld.p[b])-separate-dp[bea]-dp[b]+sum+sumy[b]) : sumy[b]);
				ll a_side = ((hld.depth[bea] <= hld.depth[hld.p[a]]) ? (hld.query(bea, hld.p[a])-separate-dp[beb]-dp[a]+sum+sumy[a]) : sumy[a]);
				// cerr<<b_side<<' '<<a_side<<'\n';
				val = separate + a_side + b_side + c;
				up(dp[x],val);
			}
			s[x]->erase(ind);
		} else {
			s[x]->ins(i.f);
		}
	}
	/* */
	assert(dp[x]>=sumy[x]);
	hld.update(x,sumy[x]-dp[x]);
		// cerr<<x<<": "<<dp[x]<<'\n';
}
bool openfile=0;
int main()
{ if(openfile)freopen("int","r",stdin);
	FAST
	cin>>n;
	FOR(i,1,n) { ll a,b;cin>>a>>b;v[a].pb(b);v[b].pb(a); }
	cin>>m;
	FOR(i,0,m) {
		cin>>Q[i].s.f>>Q[i].s.s>>Q[i].f;
	}
	lca.main(); hld.main();
	// 0-start, 1-end
	FOR(i,0,m) {
		ll a,b;tie(a,b)=Q[i].s;
		ll la=lca.lca(a,b);
		if(a!=la)at[a].pb(i,0);
		if(b!=la)at[b].pb(i,0);
		at[la].pb(i,1);
	}
	dfs(1,1);	
	cout<<dp[1]<<'\n';
}

/*
 * 
7
1 2
2 3
3 4
2 5
4 6
3 7
2
5 1 7
6 3 10

*/

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:181:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 { if(openfile)freopen("int","r",stdin);
               ~~~~~~~^~~~~~~~~~~~~~~~~

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