Submission #46889

#	Time	Username	Problem	Language	Result	Execution time	Memory
46889		qoo2p5	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	377 ms	152060 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = (int) 1e5 + 123;
const int L = 20;

int n, m;
vector<int> g[N];
int depth[N];
int up[N][L];\
int tin[N], tout[N];

int f[N];

void add(int x, int y) {
	x++;
	for (; x < N; x += x & (-x)) f[x] += y;
}

int get(int r) {
	int res = 0;
	r++;
	for (; r > 0; r -= r & (-r)) {
		res += f[r];
	}
	return res;
}

int get(int l, int r) {
	return get(r) - get(l - 1);
}

int tmr;

void precalc(int v, int p = -1) {
	if (p == -1) {
		rep(i, 0, L) up[v][i] = v;
	} else {
		up[v][0] = p;
		rep(i, 1, L) up[v][i] = up[up[v][i - 1]][i - 1];
	}
	tin[v] = tmr++;
	for (int u : g[v]) {
		if (u == p) continue;
		depth[u] = depth[v] + 1;
		precalc(u, v);
	}
	tout[v] = tmr - 1;
}

bool test(int mask, int bit) {
	return mask & (1 << bit);
}

int go(int v, int h) {
	rep(i, 0, L) if (test(h, i)) v = up[v][i];
	return v;
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	u = go(u, depth[u] - depth[v]);
	if (u == v) return u;
	per(i, L - 1, 0) {
		int uu = up[u][i];
		int vv = up[v][i];
		if (uu != vv) {
			u = uu, v = vv;
		}
	}
	return up[u][0];
}

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

int dp[N], sum[N];
vector<Q> what[N];

void solve(int v, int p = -1) {
	for (int u : g[v]) {
		if (u == p) continue;
		solve(u, v);
		sum[v] += dp[u];
	}
	maxi(dp[v], sum[v]);
	
	for (auto &q : what[v]) {
		int a = q.a;
		int b = q.b;
		if (a == v) {
			swap(a, b);
		}
		
		if (b == v) {
			int aa = go(a, depth[a] - depth[v] - 1);
			maxi(dp[v], get(tin[a]) + sum[a] + sum[v] - dp[aa] + q.c);
		} else {
			int aa = go(a, depth[a] - depth[v] - 1);
			int bb = go(b, depth[b] - depth[v] - 1);
			maxi(dp[v], get(tin[a]) + sum[a] + get(tin[b]) + sum[b] + sum[v] - dp[aa] - dp[bb] + q.c);
		}
	}
	
	for (int u : g[v]) {
		if (u == p) continue;
		add(tin[u], sum[v] - dp[u]);
		add(tout[u] + 1, -(sum[v] - dp[u]));
	}
}

void run() {
	cin >> n;
	rep(i, 0, n - 1) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	precalc(1);
	cin >> m;
	rep(i, 0, m) {
		int u, v, c;
		cin >> u >> v >> c;
		int w = lca(u, v);
		what[w].pb({u, v, c});
	}
	solve(1);
	cout << dp[1] << "\n";
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".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