oj.uz

Submission #264532

# Submission time Handle Problem Language Result Execution time Memory
264532 2020-08-14T07:30:08 Z Atalasion Election Campaign (JOI15_election_campaign) C++14
10 / 100
 273 ms 52984 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 19;

int par[N][LOG], n, q, A[N], B[N], C[N], h[N], st[N], ft[N], Time, fen[N], dp[N];
vi G[N], Q[N];

inline void add(int id, int x){
	for (; id < N; id += (id & (-id))) fen[id] += x;
}

inline int get(int id){
	int res = 0;
	for (; id > 0; id -= (id & (-id))) res += fen[id];
	return res;
}

void DFS(int v = 1, int p = 0){
	st[v] = ++Time;
	par[v][0] = p;
	for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u:G[v]){
		if (u == p)continue;
		h[u] = h[v] + 1;
		DFS(u, v);
	}
	ft[v] = Time + 1;
}

int getpar(int v, int k){
	for (int i = 0; i < LOG; i++){
		if (k & (1 << i)) v = par[v][i];
	}
	return v;
}
	
int LCA(int v, int u){
	if (h[v] < h[u]) swap(v, u);
	v = getpar(v, h[v] - h[u]);
	if (v == u) return v;
	for (int i = LOG - 1; i >= 0; i--){
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
}

void DFS2(int v = 1, int p = 0){
	int sm = 0;
	for (auto u:G[v]){
		if (u == p) continue;
		DFS2(u, v);
		sm += dp[u];
	}
	dp[v] = sm;
	for (auto u:Q[v]){
		int lca = LCA(A[u], B[u]);
		if (h[A[u]] < h[B[u]]) swap(A[u], B[u]);
		if (lca == v){
			int vv = getpar(A[u], h[A[u]] - h[v] - 1);
			dp[v] = max(dp[v], C[u] + sm - dp[vv] + get(st[A[u]]));
		}else{
			int vv = getpar(A[u], h[A[u]] - h[v] - 1), uu = getpar(B[u], h[B[u]] - h[v] - 1);
			dp[v] = max(dp[v], C[u] + sm - dp[uu] - dp[vv] + get(st[A[u]]) + get(st[B[u]]));
		}
	}
	add(st[v], sm);
	add(st[v] + 1, -sm);
	for (auto u:G[v]){
		if (u == p) continue;
		add(st[u], sm - dp[u]);
		add(ft[u], -(sm - dp[u]));
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		G[v].pb(u), G[u].pb(v);
	}
	DFS();
	cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> A[i] >> B[i] >> C[i];
		//cout << LCA(A[i], B[i]) << '\n';
		Q[LCA(A[i], B[i])].pb(i);
	}
	DFS2();	
	cout << dp[1];









	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 12 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 137 ms 37188 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 11 ms 14848 KB Output is correct
4 Correct 273 ms 52900 KB Output is correct
5 Correct 240 ms 52900 KB Output is correct
6 Correct 222 ms 52984 KB Output is correct
7 Correct 258 ms 52856 KB Output is correct
8 Correct 271 ms 52856 KB Output is correct
9 Correct 212 ms 52856 KB Output is correct
10 Correct 269 ms 52856 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 11 ms 14848 KB Output is correct
4 Correct 273 ms 52900 KB Output is correct
5 Correct 240 ms 52900 KB Output is correct
6 Correct 222 ms 52984 KB Output is correct
7 Correct 258 ms 52856 KB Output is correct
8 Correct 271 ms 52856 KB Output is correct
9 Correct 212 ms 52856 KB Output is correct
10 Correct 269 ms 52856 KB Output is correct
11 Correct 26 ms 15864 KB Output is correct
12 Correct 224 ms 52832 KB Output is correct
13 Correct 234 ms 52908 KB Output is correct
14 Correct 172 ms 52856 KB Output is correct
15 Correct 262 ms 52896 KB Output is correct
16 Correct 232 ms 52856 KB Output is correct
17 Correct 242 ms 52856 KB Output is correct
18 Correct 261 ms 52812 KB Output is correct
19 Correct 200 ms 52856 KB Output is correct
20 Correct 216 ms 52856 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 40560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 12 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 137 ms 37188 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 10 ms 14592 KB Output is correct
3 Correct 12 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 137 ms 37188 KB Output isn't correct
6 Halted 0 ms 0 KB -