Submission #239998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
239998	2020-06-17T16:48:05 Z	Knps4422	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	256 ms	29688 KB

election_campaign

//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
 
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forn(x,y) for(ll x = 1 ; x <= y ; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);

using namespace std;
 
typedef long long ll;
typedef unsigned int uint;
typedef pair<ll,ll> pll;
const int nmax = 100005;
const ll linf = 1e17;
const ll mod = 1e9+7;
const int inf = 1e9+7;
const ll lim = 1e4;

int n,m;
vec <int> g[nmax];
int tin[nmax], tout[nmax],tt=1;
int up[nmax][20];
vec < pair < pii , ll > > pth[nmax];
vec < int > vc;

void dfs(int nod, int par){
	up[nod][0] = par;
	tin[nod] = ++tt;
	for(int j : g[nod]){
		if(j != par)
		dfs(j,nod);
	}
	tout[nod] = ++tt;
}

bool anc(int a, int b){
	return ( tin[a] < tin[b] && tout[a] > tout[b]);
}

int lca(int a,  int b){
	if(anc(a,b))return a;
	int p = a;
	for(int i = 0 ; i < 20 ; i++){
		if(!anc(up[p][i],b)) p = up[p][i];
	}
	return up[p][0];
}

struct {
	ll bit[2*nmax];
	ll query(int pos){
		ll r = 0;
		for(;pos > 0; pos -= pos&-pos){
			r += bit[pos];
		}
		return r;
	}
	void update(int pos , int val){
		for(;pos <= tt ; pos += pos&-pos){
			bit[pos] += val;
		}
	}
	ll range_query(int l , int r){
		return query(r) - query(l-1);
	}

}bt1,bt2;
ll dp[nmax];

void dfs2(int nod, int par){
	for(int j : g[nod]){
		if(j != par)
				dfs2(j,nod);
	}
	ll r = 0;
	for(int j : g[nod]){
		if(j == par)continue;
		r += dp[j];
	}
	ll rez = r;
	for(auto path : pth[nod]){
		rez = max( rez, bt1.range_query(tin[nod],tin[path.fr.fr]) - bt2.range_query(tin[nod],tin[path.fr.fr]) 
			+bt1.range_query(tin[nod],tin[path.fr.sc]) - bt2.range_query(tin[nod],tin[path.fr.sc]) + r + path.sc );
	}
	dp[nod] = rez;
	bt1.update(tin[nod],r-dp[nod]);
	bt2.update(tout[nod],r-dp[nod]);
}
int main(){
	fast;
	cin >> n;
	forn(i,n-1){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1,1);

	for(int i = 1 ; i < 20 ; i++){
		forn(ii,n){
			up[ii][i] = up[up[ii][i-1]][i-1];
		}
	}
	cin >> m;
	forn(i,m){
		int a, b, c;
		cin >> a >> b >> c;
		pth[lca(a,b)].pb({{a,b},c});
	}
	dfs2(1,1);
	cout << dp[1] << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Incorrect	7 ms	4992 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Incorrect	147 ms	29688 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Incorrect	147 ms	29688 KB	Output isn't correct
5	Halted	0 ms	0 KB	-