Submission #1264644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264644		_rain_	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	95 ms	30024 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(s) (int)(s).size()
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))

template<class X,class Y>
	bool maximize(X &x ,Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x ,Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
template<class X,class Y>
	Y Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}	

const int N = (int) 1e5;
const int MAXLOG = (int) 17;
	int par[N + 2][MAXLOG + 2] = {} , h[N + 2] = {};
	vector<int>ke[N + 2];	
		void add_canh(int u , int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
		
	int n , m;
	
	void pre_dfs(int u , int p){
		par[u][0] = p;
		h[u] = h[p] + 1;
		for(int i = 1; i <= MAXLOG; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
		for(int v : ke[u]){
			if (v == p) continue;
			pre_dfs(v , u);
		}
		return;
	}

	int LCA(int u , int v){
		if (h[u] < h[v]) swap(u , v);
		for(int i = MAXLOG; i >= 0; --i){
			if (h[par[u][i]] >= h[v]) u = par[u][i];
		}
		if (u == v) return u;
		for(int i = MAXLOG; i >= 0; --i){
			if (par[u][i] != par[v][i]){
				u = par[u][i] , v = par[v][i];
			}
		}
		return par[u][0];
	}
	
	int jump(int u , int length){
		for(int i = 0; i <= MAXLOG; ++i) if (BIT(length , i)) u = par[u][i];
		return u;
	}
	
struct Node{
	int u , v;
	int a , b;
	int cost;
};

vector<Node> ask[N + 2];
	LL dp[N + 2] = {} , f[N + 2] = {};
	
	void dfs(int u , int p){
		LL tot = 0;
		
		for(int v : ke[u]){
			if (v == p) continue;
			dfs(v , u);
			tot += dp[v];
		}
		
		
		LL sum = tot;
		
		for(auto& x : ask[u]){
			LL new_c = tot - dp[x.a] - dp[x.b] + f[x.u] + f[x.v] + x.cost;
			maximize(sum , new_c);
		}
		
		dp[u] = sum;
		f[u] = tot;
		
		return;
	}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	
		
		cin >> n ;
		FOR(i , 1 , n - 1){
			int u , v; cin >> u >> v;
			add_canh(u , v);
		}	
		cin >> m;
		
		pre_dfs(1 , 0);
		
		FOR(i , 1 , m){
			int a , b , c; cin >> a >> b >> c;
			int lca = LCA(a , b);
			
			int dep_a = max(0 , h[a] - h[lca] - 1);
			int dep_b = max(0 , h[b] - h[lca] - 1);
			ask[lca].push_back({a , b , jump(a , dep_a) , jump(b , dep_b) , c});
		}
		dfs(1 , 0);
		cout << dp[1];
//		for(int i = 1; i <= n; ++i) cout << dp[i] << '\n';
	
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:107:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:108:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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