Submission #963252

#	Time	Username	Problem	Language	Result	Execution time	Memory
963252		noobcodur	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	183 ms	48064 KiB

election_campaign

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

using ld = long double;

#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;

void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}

struct Query{
	int a,b,c;
};

int bit[maxN];

void update(int idx, int val){
	while(idx < maxN){
		bit[idx] += val;
		idx += idx&-idx;
	}
}

int sum(int idx){
	int res = 0;

	while(idx > 0){
		res += bit[idx];
		idx -= idx&-idx;
	}

	return res;
}

int dp[maxN][2],tin[maxN],tout[maxN],blift[maxN][20],timer = 0;
vi graph[maxN];
vector<Query> Q[maxN];

void dfs(int src, int prev){
	tin[src] = ++timer;

	for(int ch : graph[src]){
		if(ch == prev) continue;
		blift[ch][0] = src;
		dfs(ch,src);
	}

	tout[src] = timer;
}

void dfs2(int src, int prev){
	for(int ch : graph[src]){
		if(ch == prev) continue;

		dfs2(ch,src);
		dp[src][0] += dp[ch][1];
	}

	dp[src][1] = dp[src][0];

	for(auto [a,b,cost] : Q[src]){
		dp[src][1] = max(dp[src][1],dp[src][0] + sum(tin[a]) + sum(tin[b]) + cost);
	}

	update(tin[src],dp[src][0]-dp[src][1]);
	update(tout[src]+1,dp[src][1]-dp[src][0]);
}

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

int lca(int a, int b){
	for(int j = 19; j >= 0; --j){
		if(!ancestor(blift[a][j],b)){
			a = blift[a][j];
		}
	}

	if(ancestor(a,b)) return a;

	return blift[a][0];
}

signed main(){
	setIO("");
	int n; cin >> n;
	tout[0] = INF;

	forn(i,n-1){
		int a,b; cin >> a >> b;
		graph[a].pb(b); graph[b].pb(a);
	}

	dfs(1,-1);

	forrange(j,1,20){
		forrange(i,1,n+1){
			blift[i][j] = blift[blift[i][j-1]][j-1];
		}
	}

	int m; cin >> m;

	while(m--){
		int a,b,c; cin >> a >> b >> c;
		Q[lca(a,b)].pb({a,b,c});
	}

	dfs2(1,-1);

	cout << dp[1][1] << endl;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs2(long long int, long long int)':
election_campaign.cpp:79:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |  for(auto [a,b,cost] : Q[src]){
      |           ^
election_campaign.cpp: In function 'void setIO(std::string)':
election_campaign.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((name + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((name + ".out").c_str(),"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