Submission #410057

#	Time	Username	Problem	Language	Result	Execution time	Memory
410057		luciocf	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	2 ms	1156 KiB

designated_cities

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

const int maxn = 2e3+10;
const ll inf = 1e18;

int n;
int st[maxn], en[maxn], back[maxn], pai[maxn], tt;
ll soma[maxn];

vector<int> grafo[maxn];

map<int, int> edge[maxn], mark[maxn];

struct SegmentTree
{
	pii tree[4*maxn];
	ll lazy[4*maxn];

	void build(int node, int l, int r)
	{
		lazy[node] = 0;
		if (l == r)
		{
			tree[node] = {soma[back[node]], back[node]};
			return;
		}

		int mid = (l+r)>>1;

		build(2*node, l, mid); build(2*node+1, mid+1, r);

		tree[node] = max(tree[2*node], tree[2*node+1]);
	}

	void flush(int node, int l, int r)
	{
		if (!lazy[node]) return;

		if (l != r) lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node];

		tree[node].ff += lazy[node];
		lazy[node] = 0;
	}

	void upd(int node, int l, int r, int a, int b, ll v)
	{
		flush(node, l, r);
		if (l > b || r < a) return;

		if (l >= a && r <= b)
		{
			lazy[node] = v;
			flush(node, l, r);
			return;
		}

		int mid = (l+r)>>1;

		upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

		tree[node] = max(tree[2*node], tree[2*node+1]);
	}
} seg;

ll ans[maxn], best[maxn], tot;

void dfs(int u, int p)
{
	st[u] = ++tt, back[tt] = u;

	for (auto v: grafo[u])
	{
		if (v != p)
		{
			tot += edge[v][u];
			pai[v] = u, soma[v] = soma[u] + 1ll*edge[u][v];

			dfs(v, u);
		}
	}

	en[u] = tt;
}

int root;

void fix(int u)
{
	while (u != root)
	{
		if (mark[pai[u]][u]) break;

		seg.upd(1, 1, n, st[u], en[u], -1ll*edge[pai[u]][u]);

		mark[pai[u]][u] = 1;
		u = pai[u];
	}
}

void clear(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v != p) continue;

		mark[u][v] = mark[v][u] = 0;
		clear(v, u);
	}
}

int main(void)
{
	scanf("%d", &n);

	ll tudo = 0;

	for (int i = 1; i < n; i++)
	{
		int u, v, e1, e2;
		scanf("%d %d %d %d", &u, &v, &e1, &e2);

		grafo[u].push_back(v);
		grafo[v].push_back(u);

		edge[u][v] = e1, edge[v][u] = e2;

		tudo += 1ll*(e1+e2);
	}

	for (int i = 1; i <= n; i++)
		best[i] = inf;

	for (int r = 1; r <= n; r++)
	{
		tt = 0, tot = 0, root = r, soma[r] = 0, pai[root] = 0;
		dfs(r, 0);

		seg.build(1, 1, n);

		for (int i = 1; i <= n; i++)
		{
			seg.flush(1, 1, n);
			ll w = seg.tree[1].ff;
			int u = seg.tree[1].ss;

			ans[i] = ans[i-1] + w;
			best[i] = min(best[i], tudo - ans[i-1] - tot);

			fix(u);
		}

		clear(r, 0);
	}

	int q;
	scanf("%d", &q);

	while (q--)
	{
		int t;
		scanf("%d", &t);

		printf("%lld\n", best[t]);
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf("%d %d %d %d", &u, &v, &e1, &e2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~

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