oj.uz

답안 #208376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208376 2020-03-11T04:33:11 Z achibasadzishvili Designated Cities (JOI19_designated_cities) C++14
7 / 100
 402 ms 51152 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] = mx1;
	}
}
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 361 ms 32712 KB Output is correct
3 Correct 399 ms 50512 KB Output is correct
4 Correct 321 ms 32592 KB Output is correct
5 Correct 324 ms 32464 KB Output is correct
6 Correct 333 ms 35280 KB Output is correct
7 Correct 277 ms 31484 KB Output is correct
8 Correct 402 ms 51152 KB Output is correct
9 Correct 197 ms 28980 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 361 ms 32712 KB Output is correct
3 Correct 399 ms 50512 KB Output is correct
4 Correct 321 ms 32592 KB Output is correct
5 Correct 324 ms 32464 KB Output is correct
6 Correct 333 ms 35280 KB Output is correct
7 Correct 277 ms 31484 KB Output is correct
8 Correct 402 ms 51152 KB Output is correct
9 Correct 197 ms 28980 KB Output is correct
10 Incorrect 8 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -