oj.uz

Submission #556205

# Submission time Handle Problem Language Result Execution time Memory
556205 2022-05-02T15:12:53 Z blue Designated Cities (JOI19_designated_cities) C++17
7 / 100
 195 ms 36684 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11972 KB Output is correct
2 Correct 175 ms 26416 KB Output is correct
3 Correct 194 ms 36404 KB Output is correct
4 Correct 172 ms 24928 KB Output is correct
5 Correct 176 ms 26484 KB Output is correct
6 Correct 175 ms 27748 KB Output is correct
7 Correct 153 ms 26784 KB Output is correct
8 Correct 195 ms 36684 KB Output is correct
9 Correct 116 ms 27272 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11972 KB Output is correct
2 Correct 175 ms 26416 KB Output is correct
3 Correct 194 ms 36404 KB Output is correct
4 Correct 172 ms 24928 KB Output is correct
5 Correct 176 ms 26484 KB Output is correct
6 Correct 175 ms 27748 KB Output is correct
7 Correct 153 ms 26784 KB Output is correct
8 Correct 195 ms 36684 KB Output is correct
9 Correct 116 ms 27272 KB Output is correct
10 Incorrect 6 ms 11988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB Output isn't correct
2 Halted 0 ms 0 KB -