제출 #377851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377851		pit4h	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	912 ms	61596 KiB

designated_cities

#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=1, int rr=base) {
	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();	
		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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44