Submission #114747

#	Time	Username	Problem	Language	Result	Execution time	Memory
114747		mosesmayer	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	697 ms	44792 KiB

election_campaign

#include <bits/stdc++.h>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
template<class F, class S> ostream& operator<< (ostream& os, pair<F, S> p){
	os << '{' << p.fi << ", " << p.se << '}'; return os;
}

const int mxsz = 1e5 + 3;
int n, m;
vector<int> adj[mxsz];

int dep[mxsz], par[mxsz];
int in[mxsz], out[mxsz], flat[mxsz];

namespace LCA{
	int spt[18][mxsz];
	void dfs_lca(int u, int prv = -1){
		static int tme = 0;
		in[u] = ++tme; flat[tme] = u;
		if (prv != -1) dep[u] = dep[prv] + 1;
		par[u] = spt[0][u] = prv;
		for (int nx : adj[u]){
			if (nx != prv) dfs_lca(nx, u);
		}
		out[u] = tme;
	}
	void computeST(){
		memset(spt, -1, sizeof(spt));
		dfs_lca(1);
		for (int i = 1; i <= 17; i++)
			for (int j = 1; j <= n; j++)
				if (spt[i-1][j] != -1) spt[i][j] = spt[i-1][spt[i-1][j]];
	}
	int lca(int u, int v){
		if (dep[u] < dep[v]) swap(u, v);
		for (int i = 17; i >= 0; --i)
			if (spt[i][u] != -1 && dep[spt[i][u]] >= dep[v]) u = spt[i][u];
		if (u == v) return u;
		for (int i = 17; i >= 0; --i)
			if (spt[i][u] != spt[i][v]) u = spt[i][u], v = spt[i][v];
		return spt[0][u];
	}
}

struct path{
	int l, u, v, c;
	path(){}
	path(int l, int u, int v, int c): l(l), u(u), v(v), c(c) {}
	path(int u, int v, int c): u(u), v(v), l(LCA::lca(u, v)), c(c) {};
};

#define md ((l + r) >> 1)
struct Seg{ // :^)
	int tree[mxsz << 2], lz[mxsz << 2];
	void prop(int p, int l, int r){
		if (lz[p]){
			tree[p] += lz[p];
			if (l < r){ lz[p<<1] += lz[p]; lz[p<<1|1] += lz[p]; }
			lz[p] = 0;
		}
	}
	void upd(int i, int j, int v, int p = 1, int l = 1, int r = n){
		prop(p, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){lz[p] += v; prop(p,l,r); return;}
		upd(i, j, v, p<<1, l, md);
		upd(i, j, v, p<<1|1, md+1, r);
		tree[p] = tree[p<<1] + tree[p<<1|1];
	}
	int query(int i, int p = 1, int l = 1,int r = n){
		prop(p, l, r);
		if (l == r) return tree[p];
		if (i <= md) return query(i, p<<1, l, md);
		return query(i, p<<1|1, md+1, r);
	}
} segtree; // stores the best value if we do not take any nodes from i to current
struct maxseg{
	int tree[mxsz << 2], lz[mxsz << 2];
	void prop(int p, int l, int r){
		if (lz[p]){
			if (l < r) lz[p<<1] = lz[p<<1|1] = lz[p];
			tree[p] = lz[p];
			lz[p] = 0;
		}
	}
	void upd(int i, int j, int v, int p = 1, int l = 1, int r = n){
		prop(p, l, r);
		if (j < l || i > r) return;
		if (i <= l && j >= r){lz[p] = v; prop(p,l,r); return;}
		upd(i, j, v, p<<1, l, md);
		upd(i, j, v, p<<1|1, md+1, r);
		tree[p] = max(tree[p<<1], tree[p<<1|1]);
	}
	int get(int i, int p = 1, int l = 1,int r = n){
		prop(p, l, r);
		if (l == r) return tree[p];
		if (i <= md) return get(i, p<<1, l, md);
		return get(i, p<<1|1, md+1, r);
	}
} curp;
#undef md

vector<path> pths[mxsz];

int dp[mxsz];
void dfs(int u){
	dp[u] = 0;
	for (int nx : adj[u]){
		dfs(nx);
		curp.upd(in[nx], out[nx], nx);
	}
	int tot = 0;
	for (int nx : adj[u]) tot += dp[nx];
	int mx = 0;
	for (path p : pths[u]){
		int nx = p.u, ny = p.v;
		if (nx == u) swap(nx, ny);
		mx = max(mx, segtree.query(in[nx]) + segtree.query(in[ny]) + p.c
				+ tot - dp[curp.get(in[nx])] - dp[curp.get(in[ny])]);
	}
	segtree.upd(in[u], in[u], tot);
	for (int nx : adj[u]){
		segtree.upd(in[nx], out[nx], tot - dp[nx]);
	}
	dp[u] = max(mx, tot);
}

bool cmpByIn(int u, int v){
	return in[u] < in[v];
}
int getMaximumVotes(int N, int M, vi U, vi V, vi A, vi B, vi C) {
	n = N, m = M;
	for (int i = 0; i < n-1; i++){
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	LCA::computeST();
	for (int i = 0; i < m; i++){
		path curr = path(A[i], B[i], C[i]);
		pths[curr.l].push_back(curr);
	}
	for (int i = 1; i <= n; i++){
		curp.upd(in[i], in[i], i);
		for (int j = 0, t = adj[i].size(); j < t; j++){
			// make tree level graph, remove parent
			if (dep[adj[i][j]] < dep[i]){
				swap(adj[i][j], adj[i][t-1]);
				adj[i].pop_back(); break;
			}
		}
		sort(adj[i].begin(), adj[i].end(), cmpByIn);
	}
	dfs(1);
	int mx = 0;
	for (int i = 1; i <= n; i++) mx = max(mx, dp[i]);
	return mx;
}

int main() {
  int N, M;
  std::vector<int> U, V;
  std::vector<int> A, B, C;

  scanf("%d", &N);
  U.resize(N-1); V.resize(N-1);

  for (int i = 0 ; i < N-1 ; i++) {
    scanf("%d %d", &U[i], &V[i]);
  }
  scanf("%d", &M);
  A.resize(M); B.resize(M); C.resize(M);
  for (int i = 0 ; i < M ; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
  }

  int ans = getMaximumVotes(N, M, U, V, A, B, C);
  printf("%d\n", ans);
  
  return 0;
}

Compilation message (stderr)

election_campaign.cpp: In constructor 'path::path(int, int, int)':
election_campaign.cpp:50:12: warning: 'path::v' will be initialized after [-Wreorder]
  int l, u, v, c;
            ^
election_campaign.cpp:50:6: warning:   'int path::l' [-Wreorder]
  int l, u, v, c;
      ^
election_campaign.cpp:53:2: warning:   when initialized here [-Wreorder]
  path(int u, int v, int c): u(u), v(v), l(LCA::lca(u, v)), c(c) {};
  ^~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:168:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:172:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &U[i], &V[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &M);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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