Submission #25433

#	Time	Username	Problem	Language	Result	Execution time	Memory
25433		youngyojun	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	419 ms	33716 KiB

election_campaign

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int uptwo[MAXN];
struct SEG {
	int *d; int MX;
	void init(int SZ) {
		MX = uptwo[SZ];
		d = new int[MX*2]; fill(d, d+(MX*2), 0);
	}
	void upd(int X, int R) { for(X += MX; X; X /= 2) d[X] += R; }
	int get(int S, int E) {
		int r = 0;
		for(S += MX, E += MX; S <= E; S /= 2, E /= 2) {
			if(S&1) r += d[S++]; if(~E&1) r += d[E--];
		}
		return r;
	}
};

SEG seg[MAXN];
vector<int> G[MAXN];
vector<int> L[MAXN];
int d[MAXN], csum[MAXN];
int dep[MAXN], dfscnt[MAXN], prt[MAXN][17];
int HLDsz[MAXN], HLDC[MAXN], HLDI[MAXN], HLDn;
int HLDRoot[MAXN], HLDChild[MAXN];
int EA[MAXN], EB[MAXN];
int A[MAXN], B[MAXN], C[MAXN];
int N, M;

void input() {
	scanf("%d", &N);
	for(int i = 1; i < N; i++) scanf("%d%d", &EA[i], &EB[i]);
	scanf("%d", &M);
	for(int i = 1; i <= M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
}
int lca(int a, int b) {
	if(dep[a] != dep[b]) {
		if(dep[a] > dep[b]) swap(a, b);
		const int dt = dep[b] - dep[a];
		for(int i = 0; i < 17; i++) if(dt & (1<<i)) b = prt[b][i];
	}
	if(a == b) return a;
	for(int i = 16; ~i; i--) if(prt[a][i] != prt[b][i]) {
		a = prt[a][i]; b = prt[b][i];
	}
	return prt[a][0];
}
void dfs1(int idx, int depth) {
	dep[idx] = depth; dfscnt[idx] = 1;
	for(int v : G[idx])
		if(!dep[v]) { prt[v][0] = idx; dfs1(v, depth+1); dfscnt[idx] += dfscnt[v]; }
}
void dfs2(int idx, int c, int ci) {
	HLDC[idx] = c; HLDI[idx] = ci;
	int maxcnt = -1, hubo = -1;
	for(int v : G[idx]) if(maxcnt < dfscnt[v]) { maxcnt = dfscnt[v]; hubo = v; }
	for(int v : G[idx]) {
		if(hubo == v) dfs2(v, c, ci+1);
		else dfs2(v, ++HLDn, 1);
	}
}
void precal() {
	uptwo[0] = 1; for(int i = 1; i <= N; i++) uptwo[i] = uptwo[i/2]*2;
	for(int i = 1; i < N; i++) { G[EA[i]].pb(EB[i]); G[EB[i]].pb(EA[i]); }
	dfs1(1, 1);
	for(int i = 1; i <= N; i++) vector<int>().swap(G[i]);
	for(int i = 1; i < N; i++) if(dep[EA[i]] > dep[EB[i]]) swap(EA[i], EB[i]);
	for(int i = 1; i < N; i++) G[EA[i]].pb(EB[i]);
	for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++) prt[i][j] = prt[prt[i][j-1]][j-1];
	for(int i = 1; i <= M; i++) L[lca(A[i], B[i])].pb(i);
	dfs2(1, HLDn = 1, 1);
	for(int i = 1; i <= N; i++) upmax(HLDsz[HLDC[i]], HLDI[i]);
	for(int i = 1; i <= HLDn; i++) seg[i].init(HLDsz[i]);
	for(int i = 1; i <= N; i++) if(1 == HLDI[i]) HLDRoot[HLDC[i]] = i;
	for(int i = 1; i <= N; i++) {
		int &ret = HLDChild[i]; ret = -1;
		for(int v : G[i]) if(HLDC[i] == HLDC[v]) { ret = v; break; }
	}
}
void updHLD(int idx) {
	int r = 0; for(int v : G[idx]) if(HLDC[idx] != HLDC[v]) r += d[v];
	seg[HLDC[idx]].upd(HLDI[idx], r);
}
int f(int a, int b, int c) {
	int ret = 0;
	if(a == c) swap(a, b);
	if(b == c) {
		for(; HLDC[a] != HLDC[c]; a = prt[HLDRoot[HLDC[a]]][0]) {
			if(-1 != HLDChild[a]) ret += d[HLDChild[a]];
			ret += seg[HLDC[a]].get(1, HLDI[a]);
			ret -= d[HLDRoot[HLDC[a]]];
		}
		if(a != c) {
			if(-1 != HLDChild[a]) ret += d[HLDChild[a]];
			ret += seg[HLDC[a]].get(HLDI[c], HLDI[a]);
		} else {
			ret += csum[c];
		}
	} else {
		ret = f(a, c, c) + f(b, c, c);
		ret -= csum[c];
	}
	return ret;
}
void dfs3(int idx) {
	for(int v : G[idx]) dfs3(v);
	int &ret = d[idx]; updHLD(idx);
	for(int v : G[idx]) csum[idx] += d[v];
	for(int e : L[idx]) {
		upmax(ret, f(A[e], B[e], idx) + C[e]);
	}
	upmax(ret, csum[idx]);
}
int main() {
	input(); precal(); dfs3(1);
	printf("%d\n", d[1]);
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void input()':
election_campaign.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
election_campaign.cpp:66:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < N; i++) scanf("%d%d", &EA[i], &EB[i]);
                                                          ^
election_campaign.cpp:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
                 ^
election_campaign.cpp:68:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
                                                                  ^

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