oj.uz

Submission #769722

# Submission time Handle Problem Language Result Execution time Memory
769722 2023-06-30T06:52:33 Z raysh07 Election Campaign (JOI15_election_campaign) C++17
0 / 100
 144 ms 46204 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Tree {
	vector<vector<int>> adj, lift;	
	vector<int> d, tin, tout;
	int n, timer;
	bool initialized = false;
	bool dfsed = false;

	void init(int nn){
		n = nn;
		adj.resize(n + 1);
		d.resize(n + 1);
		lift.resize(n + 1);
		tin.resize(n + 1);
		tout.resize(n + 1);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i <= n; i++) lift[i].resize(20, 0);
		initialized = true;
	}

	void addEdge(int u, int v){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void build(){
		for (int j = 1; j < 20; j++){
			for (int i = 1; i <= n; i++){
				lift[i][j] = lift[lift[i][j - 1]][j - 1];
			}
		}
	}

	void dfs(int u, int par){
		tin[u] = ++timer;
		for (int v : adj[u]){
			if (v != par){
				d[v] = d[u] + 1;
				lift[v][0] = u;
				dfs(v, u);
			}
		}
		tout[u] = ++timer;
	}

	void dfs(int root = 1){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		d[root] = 0;
		timer = 0;
		dfs(root, -1);
		build();
		dfsed = true;
	}

	int lca(int a, int b){
		if (!dfsed){
			cout << "STUPID DFS\n";
			exit(0);
		}
		if (d[a] < d[b]) swap(a, b);
		int del = d[a] - d[b];
		for (int i = 0; i < 20; i++) if (del >> i & 1) a = lift[a][i];

		if (a == b) return a;

		for (int i = 19; i >= 0; i--) if (lift[a][i] != lift[b][i]){
			a = lift[a][i];
			b = lift[b][i];
		}
		return lift[a][0];
	}

	int dist(int a, int b){
		return d[a] + d[b] - 2 * d[lca(a, b)];
	}
};

struct info{
	int u, v, w;
};

int n;
const int N = 1e5 + 69;
Tree G;
vector <info> adj[N];
int dp[N][2]; //dp[i][1] = take i, dp[i][0] = not take
int f[N];

void upd(int x, int v){
	for (int i = x; i <= 2 * n; i += i & (-i)) 
		f[i] += v;
} 

int query(int x){
	int res = 0;
	for (int i = x; i; i -= i & (-i)) res += f[i];

	return res;
}

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

void dfs(int u, int par){
	for (int v : G.adj[u]){
		if (v != par){
			dfs(v, u);
			dp[u][0] += dp[v][1];
			dp[u][1] += dp[v][1];
		}
	}

	for (auto x : adj[u]){
		dp[u][1] = max(dp[u][1], dp[u][0] + x.w - query(G.tin[u], G.tin[x.u]) - query(G.tin[u], G.tin[x.v]));
	}

	upd(G.tin[u], dp[u][1] - dp[u][0]);
	upd(G.tout[u], dp[u][0] - dp[u][1]);
}

void Solve()
{
	cin >> n;

	G.init(n);
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;

		G.addEdge(u, v);
	}

	G.dfs();

	int m; cin >> m;
	while (m--){
		int u, v, w; cin >> u >> v >> w;

		info a1;
		a1.u = u;
		a1.v = v;
		a1.w = w;
		adj[G.lca(u, v)].push_back(a1);
	}

	dfs(1, -1);

	cout << dp[1][1] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 80 ms 34304 KB Output is correct
6 Incorrect 56 ms 41292 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Incorrect 125 ms 46204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Incorrect 125 ms 46204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 80 ms 34304 KB Output is correct
6 Incorrect 56 ms 41292 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 80 ms 34304 KB Output is correct
6 Incorrect 56 ms 41292 KB Output isn't correct
7 Halted 0 ms 0 KB -