Submission #25445

#	Time	Username	Problem	Language	Result	Execution time	Memory
25445		kajebiii	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	353 ms	28000 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;


const int MAX_N = 1e5 + 10, LOG_N = 20;

int N, Q, P[LOG_N][MAX_N], D[MAX_N], St[MAX_N], En[MAX_N], Ix;
vector<int> Ed[MAX_N];
int getLCA(int a, int b) {
	if(D[a] < D[b]) swap(a, b);
	for(int p=0; p<LOG_N; p++) if((1<<p) & (D[a]-D[b])) a = P[p][a];
	if(a == b) return a;
	for(int p=LOG_N-1; p>=0; p--)
		if(P[p][a] != P[p][b]) 
			a = P[p][a], b = P[p][b];
	a = P[0][a];
	return a;
}
void dfs(int v, int p) {
	St[v] = Ix++; P[0][v] = p; D[v] = D[p] + 1;
	for(int w : Ed[v]) if(w != p) dfs(w, v);
	En[v] = Ix-1;
}

struct IDX {
	int P; vector<int> val;
	IDX() {}
	IDX(int n) {
		for(P=1; P<n; P<<=1);
		val = vector<int>(2*P, 0);
	}
	void update(int a, int b, int v) {
		a += P; b += P;
		while(a<=b) {
			if(a%2==1) val[a++] += v;
			if(b%2==0) val[b--] += v;
			a >>= 1; b >>= 1;
		}
	}
	int getAll(int v) {
		int res = val[v += P];
		while(v >>= 1) res += val[v];
		return res;
	}
}idx;

typedef tuple<int, int, int> ti;
vector<ti> Qs[MAX_N];
int getAns(int v, int p) {
	int notUse = 0;
	for(int w : Ed[v]) if(w != p) {
		notUse += getAns(w, v);
	}
	int use = notUse;
	for(ti &e : Qs[v]) {
		int x, y, c; tie(x, y, c) = e;
		use = max(use, notUse + idx.getAll(St[x]) + idx.getAll(St[y]) + c);
	}
	idx.update(St[v], En[v], notUse - use);
//	printf("%d : %d %d\n", v, notUse, use);
	return use;
}
int main() {
	cin >> N;
	REP(i, N-1) {
		int x, y; scanf("%d%d", &x, &y); 
		Ed[x].push_back(y); Ed[y].push_back(x); 
	}
	dfs(1, 0);
	idx = IDX(Ix);
	for(int p=1; p<LOG_N; p++) for(int i=1; i<=N; i++) P[p][i] = P[p-1][P[p-1][i]];
	cin >> Q;
	while(Q--) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c);
//		printf("[%d %d %d]\n", x, y, c);
		int l = getLCA(x, y);
		Qs[l].push_back(ti(x, y, c));
	}
	printf("%d\n", getAns(1, 0));
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:78:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); 
                                  ^
election_campaign.cpp:86:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, c; scanf("%d%d%d", &x, &y, &c);
                                           ^

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