oj.uz

Submission #556246

# Submission time Handle Problem Language Result Execution time Memory
556246 2022-05-02T15:59:21 Z blue Designated Cities (JOI19_designated_cities) C++17
7 / 100
 753 ms 58540 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Incorrect 7 ms 14340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 377 ms 43000 KB Output is correct
3 Correct 197 ms 31844 KB Output is correct
4 Correct 353 ms 43152 KB Output is correct
5 Correct 445 ms 44488 KB Output is correct
6 Correct 465 ms 42956 KB Output is correct
7 Correct 557 ms 49040 KB Output is correct
8 Correct 227 ms 35228 KB Output is correct
9 Correct 753 ms 58540 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13652 KB Output is correct
2 Incorrect 387 ms 49132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Incorrect 7 ms 14340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 377 ms 43000 KB Output is correct
3 Correct 197 ms 31844 KB Output is correct
4 Correct 353 ms 43152 KB Output is correct
5 Correct 445 ms 44488 KB Output is correct
6 Correct 465 ms 42956 KB Output is correct
7 Correct 557 ms 49040 KB Output is correct
8 Correct 227 ms 35228 KB Output is correct
9 Correct 753 ms 58540 KB Output is correct
10 Correct 6 ms 13652 KB Output is correct
11 Incorrect 387 ms 49132 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13652 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 7 ms 13652 KB Output is correct
4 Incorrect 7 ms 14340 KB Output isn't correct
5 Halted 0 ms 0 KB -