oj.uz

Submission #376162

# Submission time Handle Problem Language Result Execution time Memory
376162 2021-03-11T02:45:09 Z 8e7 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 610 ms 62956 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];
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];
			best[n] = max(best[n], v.ss + best[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] + (type == 1 ? 0 : best[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;
		type = t;
		dfs(1, 0);
		solve(1, 0);
		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 Incorrect 10 ms 14444 KB Output isn't correct
2 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 401 ms 38764 KB Output is correct
3 Correct 482 ms 59352 KB Output is correct
4 Correct 391 ms 38764 KB Output is correct
5 Correct 456 ms 38624 KB Output is correct
6 Correct 416 ms 41836 KB Output is correct
7 Correct 529 ms 38108 KB Output is correct
8 Correct 479 ms 59884 KB Output is correct
9 Correct 610 ms 38120 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 396 ms 38764 KB Output is correct
3 Correct 481 ms 62956 KB Output is correct
4 Correct 409 ms 39020 KB Output is correct
5 Correct 451 ms 38880 KB Output is correct
6 Correct 419 ms 42476 KB Output is correct
7 Correct 588 ms 38100 KB Output is correct
8 Correct 451 ms 52204 KB Output is correct
9 Correct 603 ms 38100 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14444 KB Output isn't correct
2 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 401 ms 38764 KB Output is correct
3 Correct 482 ms 59352 KB Output is correct
4 Correct 391 ms 38764 KB Output is correct
5 Correct 456 ms 38624 KB Output is correct
6 Correct 416 ms 41836 KB Output is correct
7 Correct 529 ms 38108 KB Output is correct
8 Correct 479 ms 59884 KB Output is correct
9 Correct 610 ms 38120 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 396 ms 38764 KB Output is correct
12 Correct 481 ms 62956 KB Output is correct
13 Correct 409 ms 39020 KB Output is correct
14 Correct 451 ms 38880 KB Output is correct
15 Correct 419 ms 42476 KB Output is correct
16 Correct 588 ms 38100 KB Output is correct
17 Correct 451 ms 52204 KB Output is correct
18 Correct 603 ms 38100 KB Output is correct
19 Correct 10 ms 14444 KB Output is correct
20 Incorrect 412 ms 38892 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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