oj.uz

Submission #556253

# Submission time Handle Problem Language Result Execution time Memory
556253 2022-05-02T16:15:52 Z blue Designated Cities (JOI19_designated_cities) C++17
100 / 100
 818 ms 67372 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 << ' ' << wtu << '\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;

			// cerr << "\n\n\n";
			// cerr << "erase leaf : " << u << ' ' << ru << '\n';

			antirep[ru].erase(z);

			actualdeg[ru]--;

			// cerr << ru << " : " << actualdeg[ru] << '\n';
			if(actualdeg[ru] == 2 && !antirep[ru].empty())
			{
				// cerr << "antirep size = " << sz(antirep[ru]) << '\n';
				// if(!antirep[ru].empty())
				auto lz = *antirep[ru].begin();
				// if(lz.rep != ru) break;
				// int u = *antirep[ru].begin();
				ll wtu = 0;

				// cerr << "modifying leaf : " << lz.u << '\n';

				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});

				// cerr << "new insert = " << u << ' ' << ru << ' ' << wtu << '\n';
			}
		}
	}


	






























	// for(int li = N; li >= 1; li--)
	// 	cerr << li << " : " << ans[li] << '\n';

	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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 10 ms 14332 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14388 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 6 ms 13652 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 498 ms 42788 KB Output is correct
3 Correct 202 ms 31692 KB Output is correct
4 Correct 495 ms 42712 KB Output is correct
5 Correct 556 ms 44300 KB Output is correct
6 Correct 491 ms 42704 KB Output is correct
7 Correct 642 ms 48836 KB Output is correct
8 Correct 276 ms 34792 KB Output is correct
9 Correct 755 ms 58308 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13652 KB Output is correct
2 Correct 513 ms 42780 KB Output is correct
3 Correct 225 ms 39764 KB Output is correct
4 Correct 488 ms 47720 KB Output is correct
5 Correct 568 ms 50416 KB Output is correct
6 Correct 477 ms 49100 KB Output is correct
7 Correct 731 ms 62324 KB Output is correct
8 Correct 359 ms 45876 KB Output is correct
9 Correct 784 ms 64372 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 10 ms 14332 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14388 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 6 ms 13652 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 13652 KB Output is correct
13 Correct 10 ms 14700 KB Output is correct
14 Correct 10 ms 13760 KB Output is correct
15 Correct 11 ms 14736 KB Output is correct
16 Correct 11 ms 14724 KB Output is correct
17 Correct 11 ms 14696 KB Output is correct
18 Correct 10 ms 14676 KB Output is correct
19 Correct 10 ms 14676 KB Output is correct
20 Correct 11 ms 14804 KB Output is correct
21 Correct 10 ms 14704 KB Output is correct
22 Correct 10 ms 14772 KB Output is correct
23 Correct 10 ms 14804 KB Output is correct
24 Correct 11 ms 14932 KB Output is correct
25 Correct 8 ms 14676 KB Output is correct
26 Correct 11 ms 14932 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 498 ms 42788 KB Output is correct
3 Correct 202 ms 31692 KB Output is correct
4 Correct 495 ms 42712 KB Output is correct
5 Correct 556 ms 44300 KB Output is correct
6 Correct 491 ms 42704 KB Output is correct
7 Correct 642 ms 48836 KB Output is correct
8 Correct 276 ms 34792 KB Output is correct
9 Correct 755 ms 58308 KB Output is correct
10 Correct 6 ms 13652 KB Output is correct
11 Correct 513 ms 42780 KB Output is correct
12 Correct 225 ms 39764 KB Output is correct
13 Correct 488 ms 47720 KB Output is correct
14 Correct 568 ms 50416 KB Output is correct
15 Correct 477 ms 49100 KB Output is correct
16 Correct 731 ms 62324 KB Output is correct
17 Correct 359 ms 45876 KB Output is correct
18 Correct 784 ms 64372 KB Output is correct
19 Correct 6 ms 13652 KB Output is correct
20 Correct 509 ms 49100 KB Output is correct
21 Correct 206 ms 39792 KB Output is correct
22 Correct 503 ms 47780 KB Output is correct
23 Correct 549 ms 49208 KB Output is correct
24 Correct 510 ms 47972 KB Output is correct
25 Correct 480 ms 49004 KB Output is correct
26 Correct 552 ms 48192 KB Output is correct
27 Correct 563 ms 50556 KB Output is correct
28 Correct 473 ms 49168 KB Output is correct
29 Correct 514 ms 47776 KB Output is correct
30 Correct 557 ms 50912 KB Output is correct
31 Correct 710 ms 57220 KB Output is correct
32 Correct 354 ms 45420 KB Output is correct
33 Correct 818 ms 64748 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13524 KB Output is correct
2 Correct 10 ms 14332 KB Output is correct
3 Correct 6 ms 13652 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 7 ms 14388 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 6 ms 13652 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 13524 KB Output is correct
13 Correct 498 ms 42788 KB Output is correct
14 Correct 202 ms 31692 KB Output is correct
15 Correct 495 ms 42712 KB Output is correct
16 Correct 556 ms 44300 KB Output is correct
17 Correct 491 ms 42704 KB Output is correct
18 Correct 642 ms 48836 KB Output is correct
19 Correct 276 ms 34792 KB Output is correct
20 Correct 755 ms 58308 KB Output is correct
21 Correct 6 ms 13652 KB Output is correct
22 Correct 513 ms 42780 KB Output is correct
23 Correct 225 ms 39764 KB Output is correct
24 Correct 488 ms 47720 KB Output is correct
25 Correct 568 ms 50416 KB Output is correct
26 Correct 477 ms 49100 KB Output is correct
27 Correct 731 ms 62324 KB Output is correct
28 Correct 359 ms 45876 KB Output is correct
29 Correct 784 ms 64372 KB Output is correct
30 Correct 7 ms 13652 KB Output is correct
31 Correct 10 ms 14700 KB Output is correct
32 Correct 10 ms 13760 KB Output is correct
33 Correct 11 ms 14736 KB Output is correct
34 Correct 11 ms 14724 KB Output is correct
35 Correct 11 ms 14696 KB Output is correct
36 Correct 10 ms 14676 KB Output is correct
37 Correct 10 ms 14676 KB Output is correct
38 Correct 11 ms 14804 KB Output is correct
39 Correct 10 ms 14704 KB Output is correct
40 Correct 10 ms 14772 KB Output is correct
41 Correct 10 ms 14804 KB Output is correct
42 Correct 11 ms 14932 KB Output is correct
43 Correct 8 ms 14676 KB Output is correct
44 Correct 11 ms 14932 KB Output is correct
45 Correct 6 ms 13652 KB Output is correct
46 Correct 509 ms 49100 KB Output is correct
47 Correct 206 ms 39792 KB Output is correct
48 Correct 503 ms 47780 KB Output is correct
49 Correct 549 ms 49208 KB Output is correct
50 Correct 510 ms 47972 KB Output is correct
51 Correct 480 ms 49004 KB Output is correct
52 Correct 552 ms 48192 KB Output is correct
53 Correct 563 ms 50556 KB Output is correct
54 Correct 473 ms 49168 KB Output is correct
55 Correct 514 ms 47776 KB Output is correct
56 Correct 557 ms 50912 KB Output is correct
57 Correct 710 ms 57220 KB Output is correct
58 Correct 354 ms 45420 KB Output is correct
59 Correct 818 ms 64748 KB Output is correct
60 Correct 6 ms 13652 KB Output is correct
61 Correct 552 ms 50320 KB Output is correct
62 Correct 238 ms 39756 KB Output is correct
63 Correct 526 ms 48928 KB Output is correct
64 Correct 521 ms 50184 KB Output is correct
65 Correct 512 ms 48832 KB Output is correct
66 Correct 538 ms 50088 KB Output is correct
67 Correct 520 ms 49068 KB Output is correct
68 Correct 565 ms 51388 KB Output is correct
69 Correct 521 ms 50244 KB Output is correct
70 Correct 471 ms 48148 KB Output is correct
71 Correct 568 ms 52308 KB Output is correct
72 Correct 702 ms 57560 KB Output is correct
73 Correct 397 ms 46384 KB Output is correct
74 Correct 806 ms 67372 KB Output is correct