Submission #409900

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409900	2021-05-21T18:43:34 Z	LucaDantas	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	958 ms	30112 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>
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 pb push_back
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

constexpr int maxn = 2e5+10;

struct Par {
	int v, w;
};

vector<Par> 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; bool ok = 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;
			}
		}
		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;
		
		vector<ll> custo;
		
		vector<pair<ll,int>> guloso;
		
		int idx = 0;
		ll custo_tot = 0;
		
		for(auto [v, w] : g[u]) {
			if(mark[v]) continue;
			ll cost = 0, gld = dfs(v, u, cost, guloso, idx) + w;
			guloso.pb({gld, idx});
			custo.pb(cost); custo_tot += cost;
			++idx;
		}

		guloso.pb({0, -1});

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

		idx = guloso.front().second;
		ans[1] = max(ans[1], custo_tot + add);

		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;

int main() {
	int n; scanf("%d", &n);
	ll tot = 0;
	for(int i = 1; i < n; i++) {
		int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
		g[a].pb({b, c});
		g[b].pb({a, d});
		tot += c + d;
	}
	// db(tot);
	centroid.decompose(1, 0);
	for(int i = 1; i <= n; i++)
		ans[i] = max(ans[i], ans[i-1]);
	int q; scanf("%d", &q);
	while(q--) {
		int e; scanf("%d", &e);
		printf("%lld\n", tot - ans[e]);
	}
}

Compilation message

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	4996 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	3 ms	4940 KB	Output is correct
2	Correct	736 ms	23468 KB	Output is correct
3	Correct	927 ms	27980 KB	Output is correct
4	Correct	732 ms	22276 KB	Output is correct
5	Correct	345 ms	23104 KB	Output is correct
6	Correct	885 ms	24832 KB	Output is correct
7	Correct	242 ms	30112 KB	Output is correct
8	Correct	958 ms	26976 KB	Output is correct
9	Correct	198 ms	29720 KB	Output is correct