oj.uz

Submission #208378

# Submission time Handle Problem Language Result Execution time Memory
208378 2020-03-11T04:34:22 Z achibasadzishvili Designated Cities (JOI19_designated_cities) C++14
16 / 100
 402 ms 53080 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;
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]){
		ans[2] = cur;
		e = ind1;
		f = ind2;
	}
	if(mx1 > dis){
		ind[x] = ind1;
		mx[x] = mx1;
	}
	else {
		ind[x] = x;
		mx[x] = dis;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	
	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);
	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:13: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:22: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:28: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 7 ms 5112 KB Output is correct
2 Incorrect 8 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 7 ms 5112 KB Output is correct
2 Correct 339 ms 30944 KB Output is correct
3 Correct 389 ms 48592 KB Output is correct
4 Correct 327 ms 30812 KB Output is correct
5 Correct 314 ms 30416 KB Output is correct
6 Correct 342 ms 33488 KB Output is correct
7 Correct 261 ms 29436 KB Output is correct
8 Correct 402 ms 49104 KB Output is correct
9 Correct 194 ms 27056 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 331 ms 32056 KB Output is correct
3 Correct 398 ms 53080 KB Output is correct
4 Correct 333 ms 32092 KB Output is correct
5 Correct 341 ms 32688 KB Output is correct
6 Correct 348 ms 35280 KB Output is correct
7 Correct 242 ms 30172 KB Output is correct
8 Correct 399 ms 43728 KB Output is correct
9 Correct 206 ms 28564 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Incorrect 8 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 7 ms 5112 KB Output is correct
2 Correct 339 ms 30944 KB Output is correct
3 Correct 389 ms 48592 KB Output is correct
4 Correct 327 ms 30812 KB Output is correct
5 Correct 314 ms 30416 KB Output is correct
6 Correct 342 ms 33488 KB Output is correct
7 Correct 261 ms 29436 KB Output is correct
8 Correct 402 ms 49104 KB Output is correct
9 Correct 194 ms 27056 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 331 ms 32056 KB Output is correct
12 Correct 398 ms 53080 KB Output is correct
13 Correct 333 ms 32092 KB Output is correct
14 Correct 341 ms 32688 KB Output is correct
15 Correct 348 ms 35280 KB Output is correct
16 Correct 242 ms 30172 KB Output is correct
17 Correct 399 ms 43728 KB Output is correct
18 Correct 206 ms 28564 KB Output is correct
19 Correct 8 ms 5112 KB Output is correct
20 Incorrect 349 ms 32080 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 5112 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -