oj.uz

Submission #204074

# Submission time Handle Problem Language Result Execution time Memory
204074 2020-02-24T08:26:45 Z ics0503 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 456 ms 66344 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121], F[212121];
void get_DF(long long w,long long bef) {
	D[w] = F[w] = 0;
	for (xy E : edge[w]) if (E.x != bef) {
		get_DF(E.x, w);
		D[w] += D[E.x] + E.y;
		F[w] = max(F[w], F[E.x] + E.z);
	}
}
long long resX[212121], resY[212121], l[212121], r[212121];
void get_res(long long w, long long bef, long long fromRoot) {
	long long sum = 0, cnt = 0;
	vector<pair<long long, long long>>L;
	for (xy E : edge[w]) if (E.x != bef) {
		sum += D[E.x] + E.y;
		L.push_back({ -(F[E.x] + E.z), E.x });
	}
	sort(L.begin(), L.end());
	resX[w] = sum + fromRoot;
	if (L.size() > 0)resY[w] = -(L[0].first) + sum + fromRoot, l[w] = w, r[w] = L[0].second;
	if (L.size() > 1)resY[w] = -(L[0].first + L[1].first) + sum + fromRoot, l[w] = L[0].second, r[w] = L[1].second;
	for (xy E : edge[w]) if (E.x != bef) get_res(E.x, w, fromRoot + sum - (D[E.x] + E.y) + E.z);
}
void dfs(long long w, long long bef) {
	for (xy E : edge[w]) if(E.x != bef) {

	}
}
long long ans[212121];
int main() {
	long long n, i, j, allsum = 0; scanf("%lld", &n);
	for (i = 0; i < n - 1; i++) {
		long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
		allsum += a; allsum += b;
		edge[s].push_back({ e, b, a });
		edge[e].push_back({ s, a, b });
	}
	get_DF(1, -1);
	get_res(1, -1, 0);
	long long rootSum = 0, root = 1;
	for (i = 1; i <= n; i++) if (ans[1] < resX[i])ans[1] = resX[i];
	for (i = 1; i <= n; i++) if (rootSum < resY[i])rootSum = resY[i], root = i;
	ans[1] = allsum - ans[1];
	ans[2] = allsum - rootSum;
	long long q, x; scanf("%lld %lld", &q, &x);
	if (q == 1 && x == 1)printf("%lld", ans[1]);
	if (q == 1 && x == 2)printf("%lld", ans[2]);
	return 0;
}

Compilation message

designated_cities.cpp: In function 'void get_res(long long int, long long int, long long int)':
designated_cities.cpp:18:21: warning: unused variable 'cnt' [-Wunused-variable]
  long long sum = 0, cnt = 0;
                     ^~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:37:18: warning: unused variable 'j' [-Wunused-variable]
  long long n, i, j, allsum = 0; scanf("%lld", &n);
                  ^
designated_cities.cpp:46:25: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  long long rootSum = 0, root = 1;
                         ^~~~
designated_cities.cpp:37:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, i, j, allsum = 0; scanf("%lld", &n);
                                 ~~~~~^~~~~~~~~~~~
designated_cities.cpp:39:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   long long s, e, a, b; scanf("%lld%lld%lld%lld", &s, &e, &a, &b);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:51:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long q, x; scanf("%lld %lld", &q, &x);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5368 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 8 ms 5368 KB Output is correct
2 Correct 378 ms 28152 KB Output is correct
3 Correct 442 ms 55416 KB Output is correct
4 Correct 352 ms 28100 KB Output is correct
5 Correct 357 ms 29360 KB Output is correct
6 Correct 377 ms 32248 KB Output is correct
7 Correct 308 ms 30628 KB Output is correct
8 Correct 456 ms 56312 KB Output is correct
9 Correct 232 ms 28460 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5368 KB Output is correct
2 Correct 372 ms 34296 KB Output is correct
3 Correct 442 ms 66344 KB Output is correct
4 Correct 360 ms 33016 KB Output is correct
5 Correct 353 ms 35632 KB Output is correct
6 Correct 385 ms 39416 KB Output is correct
7 Correct 268 ms 39064 KB Output is correct
8 Correct 413 ms 52472 KB Output is correct
9 Correct 230 ms 34508 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 378 ms 28152 KB Output is correct
3 Correct 442 ms 55416 KB Output is correct
4 Correct 352 ms 28100 KB Output is correct
5 Correct 357 ms 29360 KB Output is correct
6 Correct 377 ms 32248 KB Output is correct
7 Correct 308 ms 30628 KB Output is correct
8 Correct 456 ms 56312 KB Output is correct
9 Correct 232 ms 28460 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 372 ms 34296 KB Output is correct
12 Correct 442 ms 66344 KB Output is correct
13 Correct 360 ms 33016 KB Output is correct
14 Correct 353 ms 35632 KB Output is correct
15 Correct 385 ms 39416 KB Output is correct
16 Correct 268 ms 39064 KB Output is correct
17 Correct 413 ms 52472 KB Output is correct
18 Correct 230 ms 34508 KB Output is correct
19 Correct 8 ms 5368 KB Output is correct
20 Incorrect 373 ms 34172 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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