oj.uz

Submission #377849

# Submission time Handle Problem Language Result Execution time Memory
377849 2021-03-15T10:44:09 Z pit4h Designated Cities (JOI19_designated_cities) C++14
16 / 100
 940 ms 59596 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int MAXN = 2e5+1;
const ll INF = 1e18+1;
int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll total;
vector<pii> g[MAXN];

ll ans[MAXN];
ll cur_score, cur_val[MAXN];
void solve1(int x, int p) {
	ans[1] = max(ans[1], cur_score);
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			ll _score = cur_score, _val = cur_val[i];
			cur_score += w-cur_val[i];
			solve1(i, x);
			cur_score = _score;
			cur_val[i] = _val;
			cur_val[x] = 0;
		}
	}
}

pair<ll, int> get_furthest(int x, int p, ll dist) {
	pair<ll, int> res = mp(dist, x);
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			res = max(res, get_furthest(i, x, dist+w));
		}
	}
	return res;
}
ll get_score(int x, int p) {
	ll res = 0;
	cur_val[x] = 0;
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			res += get_score(i, x);
		}
		else {
			cur_val[x] = w;
			res += w;
		}
	}
	return res;
}
int par[MAXN], parw[MAXN], pre[MAXN], range[MAXN], nr; 
ll val[MAXN];
bool vis[MAXN];
void dfs(int x, int p, ll dist) {
	par[x] = p;
	vis[x] = 0;
	pre[x] = range[x] = ++nr;
	val[x] = dist;
	for(auto& [i, w]: g[x]) {
		if(i!=p) {
			parw[i] = w;
			dfs(i, x, dist + w);
			range[x] = max(range[x], range[i]);
		}
	}
}

const int base = (1<<18);
pair<ll, int> tree[2*base+1];
ll push[2*base+1];
void upd(int x, ll v) {
	tree[x].st += v;
	push[x] += v;
}
void ins(int l, int r, ll v, int id=1, int rl=0, int rr=base-1) {
	if(l > rr || r < rl) return;
	if(l<=rl && r>=rr) {	
		upd(id, v);
		return;
	}
	upd(id*2, push[id]), upd(id*2+1, push[id]);
	push[id] = 0;
	ins(l, r, v, id*2, rl, (rl+rr)/2), ins(l, r, v, id*2+1, (rl+rr)/2+1, rr);
	tree[id] = max(tree[id*2], tree[id*2+1]);
}
int get_best() {
	return tree[1].nd;
}
void build() {
	for(int i=1; i<=n; ++i) {
		tree[pre[i]+base-1] = mp(val[i], i);
	}
	for(int i=base-1; i>=1; --i) {
		tree[i] = max(tree[i*2], tree[i*2+1]);
	}
}
void solve(int root) {
	nr = 0;
	dfs(root, root, 0);
	build();
	vector<ll> res(n+1);
	res[1] = get_score(root, root);
	vis[root] = 1;
	for(int i=2; i<=n; ++i) {
		res[i] = res[i-1];
		int cur = get_best();	
		if(range[cur] != pre[cur]) {
			continue;
		}
		while(!vis[cur]) {
			vis[cur] = 1;
			res[i] += parw[cur];	
			ins(pre[cur], range[cur], -parw[cur]);
			cur = par[cur];
		}
	}

	for(int i=1; i<=n; ++i) {
		ans[i] = max(ans[i], res[i]);
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=0; i<n-1; ++i) {
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		g[a[i]].push_back(mp(b[i], c[i]));
		g[b[i]].push_back(mp(a[i], d[i]));
		total += c[i]+d[i];
	}
	cur_score = get_score(1, 1);
	solve1(1, 1);

	int root = get_furthest(1, 1, 0).nd;
	solve(root);

	root = get_furthest(root, root, 0).nd;
	solve(root);

	int q; cin>>q;
	for(int i=0; i<q; ++i) {
		int e; cin>>e;
		cout<<total - ans[e]<<'\n';
	}
}

Compilation message

designated_cities.cpp: In function 'void solve1(int, int)':
designated_cities.cpp:18:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |  for(auto& [i, w]: g[x]) {
      |            ^
designated_cities.cpp: In function 'std::pair<long long int, int> get_furthest(int, int, ll)':
designated_cities.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |  for(auto& [i, w]: g[x]) {
      |            ^
designated_cities.cpp: In function 'll get_score(int, int)':
designated_cities.cpp:42:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |  for(auto& [i, w]: g[x]) {
      |            ^
designated_cities.cpp: In function 'void dfs(int, int, ll)':
designated_cities.cpp:61:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |  for(auto& [i, w]: g[x]) {
      |            ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9324 KB Output is correct
2 Incorrect 8 ms 9324 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 7 ms 9324 KB Output is correct
2 Correct 607 ms 41908 KB Output is correct
3 Correct 940 ms 59596 KB Output is correct
4 Correct 463 ms 37484 KB Output is correct
5 Correct 563 ms 41828 KB Output is correct
6 Correct 619 ms 44108 KB Output is correct
7 Correct 424 ms 41952 KB Output is correct
8 Correct 886 ms 58852 KB Output is correct
9 Correct 234 ms 39696 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9324 KB Output is correct
2 Correct 606 ms 35476 KB Output is correct
3 Correct 918 ms 53452 KB Output is correct
4 Correct 488 ms 33356 KB Output is correct
5 Correct 545 ms 35524 KB Output is correct
6 Correct 624 ms 38604 KB Output is correct
7 Correct 282 ms 35904 KB Output is correct
8 Correct 797 ms 47012 KB Output is correct
9 Correct 257 ms 33088 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9324 KB Output is correct
2 Correct 607 ms 41908 KB Output is correct
3 Correct 940 ms 59596 KB Output is correct
4 Correct 463 ms 37484 KB Output is correct
5 Correct 563 ms 41828 KB Output is correct
6 Correct 619 ms 44108 KB Output is correct
7 Correct 424 ms 41952 KB Output is correct
8 Correct 886 ms 58852 KB Output is correct
9 Correct 234 ms 39696 KB Output is correct
10 Correct 8 ms 9324 KB Output is correct
11 Correct 606 ms 35476 KB Output is correct
12 Correct 918 ms 53452 KB Output is correct
13 Correct 488 ms 33356 KB Output is correct
14 Correct 545 ms 35524 KB Output is correct
15 Correct 624 ms 38604 KB Output is correct
16 Correct 282 ms 35904 KB Output is correct
17 Correct 797 ms 47012 KB Output is correct
18 Correct 257 ms 33088 KB Output is correct
19 Correct 7 ms 9324 KB Output is correct
20 Incorrect 597 ms 42032 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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