제출 #208383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208383		achibasadzishvili	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	586 ms	75600 KiB

designated_cities

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 200005
#define mp make_pair
using namespace std;
ll n,ch[N],ans[N],al,mx[N],ze[N],q,ind[N],e,f;
ll up[N],d[N],save[6*N],pown=1,fix[N],root,p[N],timer,in[N],out[N],sum,l,r,ad;
pair<ll,ll>t[6*N];
vector<pair<ll,pair<ll,ll> > >g[N];
vector<pair<pair<ll,ll> , pair<ll,ll> > > ed;
void calc1(ll x,ll par){
	for(int i=0; i<g[x].size(); i++)
		if(g[x][i].f != par){
			calc1(g[x][i].f , x);
			ch[x] += g[x][i].s.s + ch[g[x][i].f];
		}
}
void solve1(ll x,ll par,ll zed){
	ans[1] = max(ans[1] , zed + ch[x]);
	ze[x] = zed;
	for(int i=0; i<g[x].size(); i++)
		if(g[x][i].f != par)
			solve1(g[x][i].f , x , zed + ch[x] - ch[g[x][i].f] - g[x][i].s.s + g[x][i].s.f);
}
void solve2(ll x,ll par,ll dis){
	ll mx1 = 0, mx2 = 0,ind1 = x , ind2 = x;
	for(int i=0; i<g[x].size(); i++)
		if(g[x][i].f != par){
			solve2(g[x][i].f , x , dis + g[x][i].s.f);
			if(mx[g[x][i].f] > mx1)mx2 = mx1,ind2 = ind1 , mx1 = mx[g[x][i].f] , ind1 = ind[g[x][i].f];
			else if(mx[g[x][i].f] > mx2)mx2 = mx[g[x][i].f] , ind2 = ind[g[x][i].f];
		}
	ll cur = ze[x] + mx1 + mx2 - 2 * dis + ch[x];
	if(cur > ans[2]){
		root = x;
		ans[2] = cur;
		e = ind1;
		f = ind2;
	}
	if(mx1 > dis){
		ind[x] = ind1;
		mx[x] = mx1;
	}
	else {
		ind[x] = x;
		mx[x] = dis;
	}
}
void go(ll x,ll par){
	p[x] = par;
	timer++;
	in[x] = timer;
	for(int i=0; i<g[x].size(); i++)
		if(g[x][i].f != par){
			up[g[x][i].f] = g[x][i].s.f;
			d[g[x][i].f] = d[x] + g[x][i].s.f;
			go(g[x][i].f , x);
		}
	out[x] = timer;
}
void upd(ll x){
	if(!x)return;
	t[x] = max(t[2 * x] , t[2 * x + 1]);
}
void update(ll x,ll L,ll R){
	if(L > r || R < l)return;
	if(L >= l && R <= r){
		t[x].f += ad;
		save[x] += ad;
		return;
	}
	if(save[x]){
		save[2 * x] += save[x];
		save[2 * x + 1] += save[x];
		t[2 * x].f += save[x];
		t[2 * x + 1].f += save[x];
		save[x] = 0;
	}
	update(2 * x , L , (L + R) / 2);
	update(2 * x + 1 , (L + R) / 2 + 1 , R);
	t[x] = max(t[2 * x] , t[2 * x + 1]);
}
void delet(ll x){
	while(!fix[x]){
		fix[x] = 1;
		l = in[x];
		r = out[x];
		ad = -up[x];
		update(1 , 1 , pown);
		x = p[x];
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	while(pown <= n)
		pown *= 2;
	for(int i=1; i<n; i++){
		ll a,b,c,d;
		cin >> a >> b >> c >> d;
		al += c + d;
		g[a].pb(mp(b , mp(c , d)));
		g[b].pb(mp(a , mp(d , c)));
		ed.pb(mp(mp(a , b) , mp(c , d)));
	}
	
	calc1(1 , 0);
	
	solve1(1 , 0 , 0);
	solve2(1 , 0 , 0);
	
	go(root , 0);
	fix[root] = 1;
	for(int i=1; i<=n; i++){
		t[pown + in[i] - 1] = mp(d[i] , i);
		upd((pown + in[i] - 1) / 2);
	}
	delet(e);
	delet(f);
	for(int i=3; i<=n; i++){
		ans[i] = ans[i - 1] + t[1].f;
		delet(t[1].s);
	}
	
	cin >> q;
	
	while(q--){
		ll x;
		cin >> x;
		cout << al - ans[x] << '\n';
	}
	
	
	return 0;
}

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

designated_cities.cpp: In function 'void calc1(long long int, long long int)':
designated_cities.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[x].size(); i++)
               ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void solve1(long long int, long long int, long long int)':
designated_cities.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[x].size(); i++)
               ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void solve2(long long int, long long int, long long int)':
designated_cities.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[x].size(); i++)
               ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void go(long long int, long long int)':
designated_cities.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<g[x].size(); i++)
               ~^~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44