oj.uz

Submission #376191

# Submission time Handle Problem Language Result Execution time Memory
376191 2021-03-11T03:48:25 Z 8e7 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 315 ms 47468 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define ll long long
#define maxn 200005
#define pii pair<int, ll>
#define ff first
#define ss second
#define mod 1000000007
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

vector<pii> adj[maxn];

ll tup[maxn], up[maxn], best[maxn], bind[maxn];
multiset<ll> mdown[maxn];
void dfs(int n, int par) {
	for (auto v:adj[n]) {
		if (v.ff != par) {
			dfs(v.ff, n);
			tup[n] += tup[v.ff] + up[v.ff];
			if (v.ss + best[v.ff] > best[n]) {
				best[n] = v.ss + best[v.ff];
				bind[n] = bind[v.ff] == 0 ? v.ff : bind[v.ff];
			}
			//mdown[n].insert(v.ss + best[v.ff]);
		} else {
			up[n] = v.ss;
		}
	}
}
void reroot(int u, int v, ll w) {
	tup[u] -= tup[v] + up[v];
	up[u] = w;
	tup[v] += tup[u] + up[u];

	//mdown[u].erase(mdown[u].find(w + best[v]));
	//best[u] = (mdown[u].size() ? *prev(mdown[u].end()) : 0);
	//mdown[v].insert(best[u] + up[v]);
	//best[v] = max(best[v], best[u] + up[v]);
	up[v] = 0;
}
int type = 1;
ll ans = 0;
void solve(int n, int par) {
	ans = max(ans, tup[n]);
	for (auto v:adj[n]) {
		if (v.ff != par) {
			ll tmp = up[v.ff];
			reroot(n, v.ff, v.ss);
			solve(v.ff, n);
			reroot(v.ff, n, tmp);
		}
	}
}
int main() {
	io
	int n;
	cin >> n;
	ll tot = 0;
	for (int i = 0;i < n - 1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		tot += c + d;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, d));
	}

	int q;
	cin >> q;
	for (int i = 0;i < q;i++) {
		int t;
		cin >> t;
		if (t == 1) {
			dfs(1, 0);
			solve(1, 0);
		} else {
			dfs(1, 0);
			int p = bind[1];
			for (int j = 1;j <= n;j++) tup[j] = 0, up[j] = 0, best[j] = 0, bind[j] = 0;
			dfs(p, 0);
			ans = tup[p] + best[p];
		}
		cout << tot - ans << '\n';
	}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
1
2
 */

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Incorrect 10 ms 14444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 290 ms 31852 KB Output is correct
3 Correct 315 ms 44780 KB Output is correct
4 Correct 275 ms 31852 KB Output is correct
5 Correct 307 ms 31712 KB Output is correct
6 Correct 285 ms 33772 KB Output is correct
7 Correct 259 ms 31196 KB Output is correct
8 Correct 304 ms 45292 KB Output is correct
9 Correct 176 ms 28000 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 295 ms 31724 KB Output is correct
3 Correct 311 ms 47468 KB Output is correct
4 Correct 274 ms 31468 KB Output is correct
5 Correct 268 ms 31584 KB Output is correct
6 Correct 284 ms 34284 KB Output is correct
7 Correct 206 ms 30676 KB Output is correct
8 Correct 306 ms 41880 KB Output is correct
9 Correct 176 ms 30804 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Incorrect 10 ms 14444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 290 ms 31852 KB Output is correct
3 Correct 315 ms 44780 KB Output is correct
4 Correct 275 ms 31852 KB Output is correct
5 Correct 307 ms 31712 KB Output is correct
6 Correct 285 ms 33772 KB Output is correct
7 Correct 259 ms 31196 KB Output is correct
8 Correct 304 ms 45292 KB Output is correct
9 Correct 176 ms 28000 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 295 ms 31724 KB Output is correct
12 Correct 311 ms 47468 KB Output is correct
13 Correct 274 ms 31468 KB Output is correct
14 Correct 268 ms 31584 KB Output is correct
15 Correct 284 ms 34284 KB Output is correct
16 Correct 206 ms 30676 KB Output is correct
17 Correct 306 ms 41880 KB Output is correct
18 Correct 176 ms 30804 KB Output is correct
19 Correct 11 ms 14444 KB Output is correct
20 Incorrect 292 ms 31468 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Incorrect 10 ms 14444 KB Output isn't correct
3 Halted 0 ms 0 KB -