Submission #173366

#	Time	Username	Problem	Language	Result	Execution time	Memory
173366		ZwariowanyMarcin	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1298 ms	38140 KiB

designated_cities

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;

int n, nn;
int a, b, c, d;
vector <pair<int,int>> v[nax];
ll all;
ll ans[nax];

int died[nax];
int siz[nax];

void dfs(int u, int p) {
	siz[u] = 1;
	nn++;
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi]) {
			dfs(it.fi, u);
			siz[u] += siz[it.fi];
		}
}

int daj(int u, int p) {
	for(auto it : v[u]) 
		if(it.fi != p && !died[it.fi] && nn <= 2 * siz[it.fi])
			return daj(it.fi, u);
	return u;
}

ll oblicz(int u, int p) {
	ll sum = 0;
	for(auto it : v[u]) {
		if(it.fi == p) sum += it.se;
		else if(!died[it.fi])
			sum += oblicz(it.fi, u);
	}
	return sum;
}

ll dp[nax];
	
void makedp(int u, int p) {
	dp[u] = 0;
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi]) {
			makedp(it.fi, u);
			dp[u] = max(dp[u], dp[it.fi] + it.se);
		}
}

vector <pair<ll, int>> vec;

void go(int u, int p, ll cost = 0, int anc = -1) {
	tuple <ll, int, int> best = make_tuple(-1, 0, 0);
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi])
			best = max(best, make_tuple(dp[it.fi] + it.se, it.fi, it.se));
	if(get<0> (best) != -1)
		go(get<1> (best), u, cost + get<2> (best), (anc == -1 ? get<1> (best) : anc));
	else
		vec.pb(mp(cost, anc));
	for(auto it : v[u])
		if(it.fi != p && !died[it.fi] && it.fi != get<1> (best))
			go(it.fi, u, it.se, (anc == -1 ? it.fi : anc));
}

ll o[nax];
	
void solve(int u) {
	makedp(u, 0);
	go(u, 0);
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	ll pref = 0;
	for(int i = 0; i < ss(vec); ++i) {
		pref += vec[i].fi;
		ans[i + 2] = max(ans[i + 2], o[u] + pref);
	}
	int h = 0;
	while(h < ss(vec) && vec[h].se == vec[0].se)
		h++;
	if(h < ss(vec)) {
		ll cnt = vec[h].fi + vec[0].fi;
		ans[2] = max(ans[2], cnt + o[u]);
		int ile = 2;
		for(int i = 1; i < ss(vec); ++i) {
			if(i == h) continue;
			ile++;
			cnt += vec[i].fi;
			ans[ile] = max(ans[ile], cnt + o[u]);
		}
	}
	
	vec.clear();
}
	
void pro(int u, int p, ll cost) {
	ll k = 0;
	for(auto it : v[u]) {
		if(it.fi != p)
			;
		else
			k = it.se;
	}
	cost -= k;
	o[u] = cost;
	ans[1] = max(ans[1], o[u]);
	for(auto it : v[u])
		if(it.fi != p)
			pro(it.fi, u, cost + it.se);
}
			

void decomp(int u) {
	nn = 0;
	dfs(u, 0);
	int c = daj(u, 0);
	solve(c);
	died[c] = 1;
	for(auto it : v[c])
		if(!died[it.fi])
			decomp(it.fi);
}
	
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, d));
		all += c + d;
	}
	
	o[1] = oblicz(1, 0);
	pro(1, 0, o[1]);
	
	decomp(1);
	
	for(int i = 1; i <= n; ++i)
		ans[i] = max(ans[i], ans[i - 1]);
	
	int q;
	scanf("%d", &q);
	while(q--) {
		scanf("%d", &a);
		printf("%lld\n", all - ans[a]);
	}
	

	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:155:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44