oj.uz

Submission #208383

# Submission time Handle Problem Language Result Execution time Memory
208383 2020-03-11T05:01:01 Z achibasadzishvili Designated Cities (JOI19_designated_cities) C++17
16 / 100
 586 ms 75600 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Incorrect 7 ms 5112 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 8 ms 5112 KB Output is correct
2 Correct 404 ms 52480 KB Output is correct
3 Correct 586 ms 73424 KB Output is correct
4 Correct 392 ms 49872 KB Output is correct
5 Correct 376 ms 49616 KB Output is correct
6 Correct 493 ms 58168 KB Output is correct
7 Correct 320 ms 48340 KB Output is correct
8 Correct 572 ms 74064 KB Output is correct
9 Correct 229 ms 45624 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 396 ms 51936 KB Output is correct
3 Correct 571 ms 75600 KB Output is correct
4 Correct 390 ms 49232 KB Output is correct
5 Correct 363 ms 49360 KB Output is correct
6 Correct 498 ms 57936 KB Output is correct
7 Correct 240 ms 46672 KB Output is correct
8 Correct 564 ms 66644 KB Output is correct
9 Correct 217 ms 44852 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 404 ms 52480 KB Output is correct
3 Correct 586 ms 73424 KB Output is correct
4 Correct 392 ms 49872 KB Output is correct
5 Correct 376 ms 49616 KB Output is correct
6 Correct 493 ms 58168 KB Output is correct
7 Correct 320 ms 48340 KB Output is correct
8 Correct 572 ms 74064 KB Output is correct
9 Correct 229 ms 45624 KB Output is correct
10 Correct 8 ms 5112 KB Output is correct
11 Correct 396 ms 51936 KB Output is correct
12 Correct 571 ms 75600 KB Output is correct
13 Correct 390 ms 49232 KB Output is correct
14 Correct 363 ms 49360 KB Output is correct
15 Correct 498 ms 57936 KB Output is correct
16 Correct 240 ms 46672 KB Output is correct
17 Correct 564 ms 66644 KB Output is correct
18 Correct 217 ms 44852 KB Output is correct
19 Correct 7 ms 5112 KB Output is correct
20 Incorrect 394 ms 51640 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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