Submission #556246

#	Time	Username	Problem	Language	Result	Execution time	Memory
556246		blue	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	753 ms	58540 KiB

designated_cities

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int mx = 200'000;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000'000LL;

int N;
vi A(1+mx), B(1+mx);
vll C(1+mx), D(1+mx);

vi edge[1+mx];

int L = 0;








ll basicCost = 0;
vll delta = vll(1+mx, 0);
vi vis = vi(1+mx, 0);


void dfs(int u, int p)
{
	vis[u] = 1;
	for(int e : edge[u])
	{
		int v = A[e] + B[e] - u;

		if(vis[v]) continue;

		if(v == B[e])
		{
			basicCost += C[e];
			delta[v] = delta[u] + D[e] - C[e];
		}
		else
		{
			basicCost += D[e];
			delta[v] = delta[u] + C[e] - D[e];
		}

		dfs(v, u);
	}
}









vi deg(1+mx, 0);






vi owner(1+mx-1, 0);


struct leaf
{
	int u; //leaf node-index
	int rep; //head of chain
	ll wt = 0;
};

bool operator < (leaf A, leaf B)
{
	return vll{A.wt, A.u} < vll{B.wt, B.u};
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for(int e = 1; e <= N-1; e++)
	{
		cin >> A[e] >> B[e] >> C[e] >> D[e];
		edge[A[e]].push_back(e);
		edge[B[e]].push_back(e);
	}

	for(int i = 1; i <= N; i++)
		L += (sz(edge[i]) == 1);

	vll ans(1+N, INF);





	//Part 1: E = 1
	dfs(1, 0);
	for(int i = 1; i <= N; i++)
		ans[1] = min(ans[1], basicCost + delta[i]);


















	//Part 2: E > 1






	for(int l = L; l <= N; l++)
		ans[l] = 0;



	for(int i = 1; i <= N; i++)
		deg[i] = sz(edge[i]);












	if(L >= 3)
	{
		queue<int> tbv;

		set<leaf> leaves;

		vi edgevis(1+N, 0);

		for(int i = 1; i <= N; i++)
		{
			if(deg[i] == 1)
			{
				tbv.push(i);
			}
		}

		set<leaf> antirep[1+N];




	// cerr << "done\n";

		vi actualdeg = deg;

		while(!tbv.empty())
		{
			int u = tbv.front();
			tbv.pop();

			// cerr << "u = " << u << '\n';

			ll wtu = 0LL;

			int ru = u;
			while(1)
			{
				bool nxt = 0;
				for(int e : edge[ru])
				{
					if(edgevis[e]) continue;

					edgevis[e] = 1;

					ru = A[e] + B[e] - ru;

					if(A[e] == ru)
						wtu += C[e];
					else
						wtu += D[e];

					if(deg[ru] != 2)
						break;

					nxt = 1;
				}

				if(nxt == 0) break;
			}

			leaves.insert({u, ru, wtu});
			// cerr << "inserting leaf :  " << u << ' ' << ru << '\n';
			antirep[ru].insert({u, ru, wtu});
		}

		// cerr << sz(leaves) << '\n';




		for(int li = L-1; li >= 2; li--)
		{
			leaf z = *leaves.begin();

			leaves.erase(leaves.begin());

			ans[li] = ans[li+1] + z.wt;

			if(li == 2) break;

			int u = z.u;
			ll wtu = z.wt;
			int ru = z.rep;

			antirep[ru].erase(z);

			actualdeg[ru]--;

			if(actualdeg[ru] == 1)
			{
				auto lz = *antirep[ru].begin();
				// int u = *antirep[ru].begin();
				ll wtu = 0;

				antirep[ru].erase(lz);
				leaves.erase(lz);

				u = lz.u;
				wtu = lz.wt;
				ru = lz.rep;

				while(1)
				{
					bool nxt = 0;
					for(int e : edge[ru])
					{
						if(edgevis[e]) continue;

						edgevis[e] = 1;

						ru = A[e] + B[e] - ru;

						if(A[e] == ru)
							wtu += C[e];
						else
							wtu += D[e];

						if(actualdeg[ru] != 2)
							break;

						nxt = 1;
					}

					if(nxt == 0) break;
				}

				antirep[ru].insert({u, ru, wtu});
				leaves.insert({u, ru, wtu});
			}
		}
	}


	
































	int Q;
	cin >> Q;

	for(int q = 1; q <= Q; q++)
	{
		int E;
		cin >> E;

		cout << ans[E] << '\n';
	}
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:245:7: warning: unused variable 'wtu' [-Wunused-variable]
  245 |    ll wtu = z.wt;
      |       ^~~

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