oj.uz

Submission #264499

# Submission time Handle Problem Language Result Execution time Memory
264499 2020-08-14T07:16:28 Z Atalasion Election Campaign (JOI15_election_campaign) C++14
10 / 100
 184 ms 32504 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")


using namespace std;

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

const int N = 100000 + 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 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Incorrect 99 ms 17784 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 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Correct 149 ms 32376 KB Output is correct
5 Correct 156 ms 32376 KB Output is correct
6 Correct 134 ms 32336 KB Output is correct
7 Correct 146 ms 32376 KB Output is correct
8 Correct 161 ms 32376 KB Output is correct
9 Correct 148 ms 32376 KB Output is correct
10 Correct 184 ms 32312 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Correct 149 ms 32376 KB Output is correct
5 Correct 156 ms 32376 KB Output is correct
6 Correct 134 ms 32336 KB Output is correct
7 Correct 146 ms 32376 KB Output is correct
8 Correct 161 ms 32376 KB Output is correct
9 Correct 148 ms 32376 KB Output is correct
10 Correct 184 ms 32312 KB Output is correct
11 Correct 15 ms 5760 KB Output is correct
12 Correct 172 ms 32332 KB Output is correct
13 Correct 163 ms 32376 KB Output is correct
14 Correct 151 ms 32376 KB Output is correct
15 Correct 182 ms 32504 KB Output is correct
16 Correct 160 ms 32376 KB Output is correct
17 Correct 160 ms 32380 KB Output is correct
18 Correct 165 ms 32376 KB Output is correct
19 Correct 140 ms 32376 KB Output is correct
20 Correct 150 ms 32376 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Incorrect 99 ms 17784 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Incorrect 99 ms 17784 KB Output isn't correct
6 Halted 0 ms 0 KB -