Submission #556205

#	Time	Username	Problem	Language	Result	Execution time	Memory
556205		blue	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	195 ms	36684 KiB

designated_cities

#include <iostream>
#include <vector>
#include <algorithm>
#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);
	}
}









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

	int Q;
	cin >> Q;

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

		if(E == 1) 
			cout << ans[1] << '\n';
	}


}

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