oj.uz

답안 #208372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208372 2020-03-11T03:56:24 Z achibasadzishvili Designated Cities (JOI19_designated_cities) C++17
0 / 100
 643 ms 106232 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,cur,ans,m[200005],b[200005],mx[2005][2005],bb[200005],an[200005],leaf[200005],ind = 1;
vector<pair<ll,pair<ll,ll> > >v[200004];
void go(ll x,ll par,ll dist){
	m[x] = dist;
	if(v[x].size() == 1 && x != ind)leaf[x] = 1;
	for(int i=0; i<v[x].size(); i++){
		if(v[x][i].f != par){
			go(v[x][i].f,x,dist + v[x][i].s.f);
			b[x] += b[v[x][i].f] + v[x][i].s.s;
			leaf[x] += leaf[v[x][i].f];
		}
	}
}
void findans(ll x,ll par,ll win){
	an[1] = max(an[1],win + m[x] + b[x]);
	vector<ll>p;
	for(int i=0; i<v[x].size(); i++){
		if(v[x][i].f != par){
			findans(v[x][i].f,x,win + b[x] - b[v[x][i].f] - v[x][i].s.s);
			mx[1][v[x][i].f] +=  v[x][i].s.f;
			for(int j=1; j<=leaf[v[x][i].f]; j++){
				p.pb(mx[j][v[x][i].f]);
			}
		}
	}
	//cout << x << " " << mx1[x] << " " << mx2[x] << endl;
	ll raod = 0;
	sort(p.begin(),p.end());
	reverse(p.begin(),p.end());
//	cout << x << endl;
	for(int i=0; i<p.size(); i++){
	//	cout << p[i] << " ";
		raod += p[i];
		mx[i+1][x] = p[i];
		if(i>0)an[i+1] = max(an[i+1],raod + b[x] + win + m[x]);
	}
//	cout << endl;
}
int main(){
	cin >> n;
	
	for(int i=1; i<n; i++){
		ll x,y,z,t;
		cin >> x >> y >> z >> t;
		ans += z + t;
		v[x].pb({y,{z,t}});
		v[y].pb({x,{t,z}});
		if(v[x].size() >= 2)ind = x;
		if(v[y].size() >= 2)ind = y;
	}
	
	go(ind,-1,0);
	
	findans(ind,-1,0);
	
	for(int i=1; i<=n; i++){
		an[i] = max(an[i],an[i-1]);
	}
	ll q;
	cin >> q;
	
	while(q--){
		ll x;
		cin >> x;
		cout << ans - an[x] << endl;
	}
	
	
	
	
	return 0;
}

Compilation message

designated_cities.cpp: In function 'void go(long long int, long long int, long long int)':
designated_cities.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v[x].size(); i++){
               ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void findans(long long int, long long int, long long int)':
designated_cities.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v[x].size(); i++){
               ~^~~~~~~~~~~~
designated_cities.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<p.size(); i++){
               ~^~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5064 KB Output is correct
2 Runtime error 643 ms 106232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5064 KB Output is correct
2 Runtime error 643 ms 106232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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