Submission #1308608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308608		arashmemar	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	407 ms	71732 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;

vector <pair <int, int>> ne[maxn];
set <pair <int, int>> sne[maxn];
int c[2 * maxn];

set <pair <long long int, int>> mn;

long long int ans[maxn], pl[maxn], ans1 = 1e18, cur;

set <int> act[maxn];

int abv[maxn];

void init(int v)
{
	int t = v;
	while (sne[v].size() == 1 and ne[v].size() < 3)
	{
		int u = (*sne[v].begin()).first;
		int w = ((*sne[v].begin()).second ^ 1);
		sne[u].erase(make_pair(v, w));
		pl[t] += c[w];
		v = u;
	}
	act[v].insert(t);
	abv[t] = v;
	mn.insert({pl[t], t});
}

void update(int v, int t)
{
	if (act[v].size() > 1)
	{
		return ;
	}
	act[v].clear();
	mn.erase({pl[t], t});

	while (act[v].size() == 0 and sne[v].size() == 1)
	{
		int u = (*sne[v].begin()).first;
		int w = ((*sne[v].begin()).second ^ 1);
		sne[u].erase(make_pair(v, w));
		pl[t] += c[w];
		v = u;
	}
	act[v].insert(t);
	abv[t] = v;
	mn.insert({pl[t], t});
	return ;
}

void del()
{
	int v = (*mn.begin()).second;
	mn.erase(mn.begin());
	act[abv[v]].erase(v);
	v = abv[v];
	if (act[v].empty())
	{
		return ;
	}
	int t = *act[v].begin();
	update(v, t);
	return ;
}


bool mark[maxn];

void calc(int v)
{
	mark[v] = 1;
	for (auto o : ne[v])
	{
		int u = o.first, w = o.second;
		if (mark[u])
		{
			continue;
		}
		cur += c[w];
		calc(u);
	}
	mark[v] = 0;
	return ;
}

void dfs(int v)
{
	ans1 = min(ans1, cur);
	mark[v] = 1;
	for (auto o : ne[v])
	{
		int u = o.first, w = o.second;
		if (mark[u])
		{
			continue;
		}
		cur += c[w ^ 1] - c[w];
		dfs(u);
		cur += c[w] - c[w ^ 1];
	}
	return ;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0;i < n - 1;i++)
	{
		int v, u;
		cin >> v >> u >> c[2 * i] >> c[2 * i + 1];
		sne[v].insert({u, 2 * i});
		sne[u].insert({v, 2 * i + 1});
		ne[v].push_back({u, 2 * i});
		ne[u].push_back({v, 2 * i + 1});
	}

	int nob = 0;
	for (int i = 1;i <= n;i++)
	{
		if (ne[i].size() == 1)
		{
			init(i);
			nob++;
		}
	}

	while (nob > 2)
	{
		nob--;
		ans[nob] = ans[nob + 1] + (*mn.begin()).first;
		del();
	}

	int q;
	cin >> q;

	calc(1);
	dfs(1);

	while (q--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			cout << ans1 << '\n';
		}
		else
		{
			cout << ans[t] << '\n';
		}
	}
}

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