oj.uz

Submission #264509

# Submission time Handle Problem Language Result Execution time Memory
264509 2020-08-14T07:21:29 Z Atalasion Election Campaign (JOI15_election_campaign) C++14
10 / 100
 264 ms 53028 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 9 ms 14592 KB Output is correct
3 Correct 9 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 130 ms 37256 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 11 ms 14592 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 10 ms 14848 KB Output is correct
4 Correct 214 ms 52812 KB Output is correct
5 Correct 219 ms 52984 KB Output is correct
6 Correct 170 ms 52856 KB Output is correct
7 Correct 203 ms 52836 KB Output is correct
8 Correct 209 ms 53028 KB Output is correct
9 Correct 195 ms 52904 KB Output is correct
10 Correct 251 ms 52856 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14592 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 10 ms 14848 KB Output is correct
4 Correct 214 ms 52812 KB Output is correct
5 Correct 219 ms 52984 KB Output is correct
6 Correct 170 ms 52856 KB Output is correct
7 Correct 203 ms 52836 KB Output is correct
8 Correct 209 ms 53028 KB Output is correct
9 Correct 195 ms 52904 KB Output is correct
10 Correct 251 ms 52856 KB Output is correct
11 Correct 24 ms 15744 KB Output is correct
12 Correct 229 ms 52984 KB Output is correct
13 Correct 240 ms 52860 KB Output is correct
14 Correct 206 ms 52984 KB Output is correct
15 Correct 231 ms 52856 KB Output is correct
16 Correct 207 ms 52956 KB Output is correct
17 Correct 253 ms 52984 KB Output is correct
18 Correct 226 ms 52860 KB Output is correct
19 Correct 180 ms 52856 KB Output is correct
20 Correct 264 ms 52984 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 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 9 ms 14592 KB Output is correct
3 Correct 9 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 130 ms 37256 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 9 ms 14592 KB Output is correct
3 Correct 9 ms 14592 KB Output is correct
4 Correct 10 ms 14720 KB Output is correct
5 Incorrect 130 ms 37256 KB Output isn't correct
6 Halted 0 ms 0 KB -