Submission #208372

#	Time	Username	Problem	Language	Result	Execution time	Memory
208372		achibasadzishvili	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	643 ms	106232 KiB

designated_cities

#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 (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44