제출 #1264673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264673		_rain_	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	191 ms	35316 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] = {};
	int sta[N + 2] = {} , fin[N + 2] = {} , time_dfs = 0;
	vector<int>ke[N + 2];	
		void add_canh(int u , int v){
			ke[u].push_back(v) , ke[v].push_back(u);
			return;
		}
	struct Node{
		int u , v , c;
	};
	vector<Node> ask[N + 2];
		
	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];
		
		sta[u] = ++time_dfs;
	
		for(int v : ke[u]){
			if (v == p) continue;
			pre_dfs(v , u);
		}
	
		fin[u] = time_dfs;
		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];
	}
	
	
class IT{
	public:
		vector<LL>st;
		void load_size(int n){
			st = vector<LL>(n * 4 + 2 , 0);
			return;
		}
		void update(int id , int l , int r , int pos , LL val){
			if (l > pos || r < pos) return;
			if (l == r) st[id] += val;
			else{
				int m = (l + r) / 2;
				if (pos <= m) update(id * 2 , l , m , pos , val);
					else update(id * 2 + 1 , m + 1 , r , pos , val);
					
				st[id] = st[id * 2] + st[id * 2 + 1];
			}
			return;
		}
		LL Get(int id , int l , int r , int u , int v){
			if (l > v || r < u) return 0;
			if (u <= l && r <= v) return st[id];
			int m = (l + r) / 2;
			return Get(id * 2 , l , m , u , v) + Get(id * 2 + 1 , m + 1 , r , u , v);
		}
};
IT st;

	LL dp[N + 2] = {};
	
		void add_range(int u , LL cost){
			st.update(1 , 1 , time_dfs , sta[u] , cost);
			st.update(1 , 1 , time_dfs , fin[u] + 1 , -cost);
			return;
		}
		
		LL Get(int u){
			return st.Get(1 , 1 , time_dfs , 1 , sta[u]);
		}

	void dfs(int u , int p){
		LL tot = 0;
		for(int v : ke[u]){
			if (v == p) continue;
			dfs(v , u);
			tot += dp[v];
		}
		
		add_range(u , tot);
		dp[u] = tot;
		for(auto &  x : ask[u]){
			LL new_c =  Get(x.u) + Get(x.v) - Get(u)  + x.c;
			maximize(dp[u] , new_c);
		}
		add_range(u , -dp[u]);
		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);
		st.load_size(time_dfs);
		
//		for(int i = 1; i <= n; ++i) cout << sta[i] << ' ' << fin[i] << '\n';
		
		FOR(i , 1 , m){
			int a , b , c; cin >> a >> b >> c;
			int lca = LCA(a , b);
			ask[lca].push_back({a , b , c});
		}
		dfs(1 , 0);
		cout << dp[1] << '\n';
//		for(int i = 1; i <= n; ++i) cout << dp[i] << '\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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