Submission #409940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409940	2021-05-21T19:32:57 Z	LucaDantas	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	1326 ms	52484 KB

designated_cities

// Se eu pegar um cara qualquer e definir que ele vai ser um resort e minha raiz
// eu posso fazer um guloso escolhendo sempre o cara mais fundo e atualizando a profundidade
// dos outros, o problema é que eu nao necessariamente preciso pegar essa raiz
// entao eu teria q brutar todas as possiveis, o que ficaria n^2, já pega n<=2000 though
// Faço um centroid e em cada nivel eu escolho sempre caras de pelo menos duas subarvores
// diferentes, se a melhor resposta n tiver ai so descer nos filhos e ta safe
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

// template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
// template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

// #ifdef MY_DEBUG_FLAG
// void debug() { cerr << endl; }
// template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
// #define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
// #else
// #define db(...) 1
// #endif

using ll = long long;

#define int ll

#define pb push_back
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

constexpr int maxn = 2e5+10;

vector<pair<int,int>> g[maxn];

ll ans[maxn];

struct Centroid {
	bool mark[maxn]; int sz[maxn];
	void pre(int u, int p = 0) {
		sz[u] = 1;
		for(auto [v, w] : g[u]) if(!mark[v] && v != p)
			pre(v, u), sz[u] += sz[v];
	}
	int get(int u) {
		for(auto [v, w] : g[u]) if((sz[v] << 1) > sz[u] && !mark[v])
			return (sz[u] -= sz[v], sz[v] += sz[u], get(v));
		return u;
	}
	ll dfs(int u, int p, ll& cost, vector<pair<ll,int>>& guloso, int idx) {
		vector<ll> td;
		ll maior = 0;
		for(auto [v, w] : g[u]) {
			if(v == p) cost += w;
			else if(!mark[v]) {
				ll gld = dfs(v, u, cost, guloso, idx) + w;
				td.pb(gld);
				if(gld > maior) maior = gld;
			}
		}
		bool ok = 0;
		for(ll a : td) {
			if(a == maior && !ok) ok = 1;
			else guloso.pb({a, idx});
		}
		return maior;
	}
	void decompose(int u, ll add) {
		pre(u); u = get(u);

		mark[u] = 1;
		
		static vector<ll> custo; custo.clear();
		
		static vector<pair<ll,int>> guloso; guloso.clear();
		
		int idx = 0;
		ll custo_tot = 0;
		
		guloso.pb({0, -1});
		for(auto [v, w] : g[u]) {
			if(mark[v]) continue;
			ll cost = 0;
			ll gld = dfs(v, u, cost, guloso, idx) + w;
			guloso.pb({gld, idx});
			custo.pb(cost); custo_tot += cost;
			++idx;
		}

		// db(u, add, guloso, custo, custo_tot);
		
		sort(all(guloso));
		reverse(all(guloso));

		// ans[1] = max(ans[1], custo_tot + add);

		idx = guloso.front().second;

		int primeiro = 0;
		for(int i = 0; i < sz(guloso); i++)
			if(guloso[i].second != idx) { primeiro = i; break; }
		
		ll bom = custo_tot, foi = guloso[primeiro].first;
		
		for(int i = 0; i < sz(guloso); i++) {
			bom += guloso[i].first;
			if(primeiro == i) foi = 0;
			ans[i + 1 + (foi>0)] = max(ans[i + 1 + (foi>0)], bom + foi + add);
		}

		ll val = 0;

		vector<ll> suf;
		for(int i = sz(custo)-1; i >= 0; i--)
			suf.pb(val), val += custo[i];
		reverse(all(suf));

		val = 0;
		int i = 0;
		for(auto [v, w] : g[u]) {
			if(mark[v]) continue;
			decompose(v, val + suf[i] + w);
			val += custo[i];
			++i;
		}
	}
} centroid;

ll aq[maxn];

struct AAA
{
	int v, w, back;
};

vector<AAA> g_esp[maxn];

void pre_caso1(int u, int p) {
	// fprintf(stderr, "pre %lld\n", u);
	for(auto [v, w, back] : g_esp[u]) {
		if(v == p) continue;
		pre_caso1(v, u);
		aq[u] += aq[v] + back;
	}
	// fprintf(stderr, "pre %lld %lld\n", u, aq[u]);
}

void caso1(int u, int p) {
	// fprintf(stderr, "noraml %lld %lld\n", u, aq[u]);
	ans[1] = max(ans[1], aq[u]);
	for(auto [v, w, back] : g_esp[u]) {
		if(v == p) continue;
		aq[v] = w + aq[u] - back;
		// fprintf(stderr, "uv %lld %lld %lld %lld\n", u, v, aq[v], aq[v]);
		caso1(v, u);
	}
}

int32_t main() {
	int n; scanf("%lld", &n);
	ll tot = 0;
	for(int i = 1; i < n; i++) {
		int a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
		g[a].pb({b, c});
		g[b].pb({a, d});
		tot += c + d;

		g_esp[a].pb({b, c, d});
		g_esp[b].pb({a, d, c});
	}

	centroid.decompose(1, 0);
	for(int i = 1; i <= n; i++)
		ans[i] = max(ans[i], ans[i-1]);

	pre_caso1(1, 0);
	caso1(1, 0);

	int q; scanf("%lld", &q);
	while(q--) {
		int e; scanf("%lld", &e);
		printf("%lld\n", tot - ans[e]);
	}
}

Compilation message

designated_cities.cpp: In function 'int32_t main()':
designated_cities.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |  int n; scanf("%lld", &n);
      |         ~~~~~^~~~~~~~~~~~
designated_cities.cpp:165:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   int a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |  int q; scanf("%lld", &q);
      |         ~~~~~^~~~~~~~~~~~
designated_cities.cpp:183:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   int e; scanf("%lld", &e);
      |          ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	9676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	9676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9676 KB	Output is correct
2	Correct	965 ms	39232 KB	Output is correct
3	Correct	1197 ms	52484 KB	Output is correct
4	Correct	945 ms	39128 KB	Output is correct
5	Correct	490 ms	40348 KB	Output is correct
6	Correct	1149 ms	41772 KB	Output is correct
7	Correct	311 ms	44464 KB	Output is correct
8	Correct	1326 ms	47888 KB	Output is correct
9	Correct	308 ms	43728 KB	Output is correct