oj.uz

Submission #208375

# Submission time Handle Problem Language Result Execution time Memory
208375 2020-03-11T04:25:19 Z achibasadzishvili Designated Cities (JOI19_designated_cities) C++17
16 / 100
 403 ms 53328 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;
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;
	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 , mx1 = mx[g[x][i].f];
			else if(mx[g[x][i].f] > mx2)mx2 = mx[g[x][i].f];
		}
	ans[2] = max(ans[2] , ze[x] + mx1 + mx2 - 2 * dis + ch[x]);
	mx[x] = max(mx1 , 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 4984 KB Output is correct
2 Incorrect 7 ms 4984 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 4984 KB Output is correct
2 Correct 340 ms 29988 KB Output is correct
3 Correct 388 ms 45264 KB Output is correct
4 Correct 326 ms 30176 KB Output is correct
5 Correct 309 ms 29776 KB Output is correct
6 Correct 339 ms 32352 KB Output is correct
7 Correct 275 ms 28776 KB Output is correct
8 Correct 397 ms 46032 KB Output is correct
9 Correct 182 ms 26288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 341 ms 35536 KB Output is correct
3 Correct 403 ms 53328 KB Output is correct
4 Correct 326 ms 34072 KB Output is correct
5 Correct 336 ms 35920 KB Output is correct
6 Correct 347 ms 38096 KB Output is correct
7 Correct 235 ms 33516 KB Output is correct
8 Correct 384 ms 45652 KB Output is correct
9 Correct 192 ms 31544 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Incorrect 7 ms 4984 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 4984 KB Output is correct
2 Correct 340 ms 29988 KB Output is correct
3 Correct 388 ms 45264 KB Output is correct
4 Correct 326 ms 30176 KB Output is correct
5 Correct 309 ms 29776 KB Output is correct
6 Correct 339 ms 32352 KB Output is correct
7 Correct 275 ms 28776 KB Output is correct
8 Correct 397 ms 46032 KB Output is correct
9 Correct 182 ms 26288 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 341 ms 35536 KB Output is correct
12 Correct 403 ms 53328 KB Output is correct
13 Correct 326 ms 34072 KB Output is correct
14 Correct 336 ms 35920 KB Output is correct
15 Correct 347 ms 38096 KB Output is correct
16 Correct 235 ms 33516 KB Output is correct
17 Correct 384 ms 45652 KB Output is correct
18 Correct 192 ms 31544 KB Output is correct
19 Correct 8 ms 4984 KB Output is correct
20 Incorrect 333 ms 35464 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 4984 KB Output is correct
2 Incorrect 7 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -