oj.uz

Submission #204073

# Submission time Handle Problem Language Result Execution time Memory
204073 2020-02-24T08:05:15 Z ics0503 Designated Cities (JOI19_designated_cities) C++17
7 / 100
 357 ms 38648 KB 
#include<stdio.h>
#include<vector>
using namespace std;
struct xy { long long x, y, z; };
vector<xy>edge[212121];
long long D[212121];
void get_D(long long w,long long bef) {
	D[w] = 0;
	for (xy E : edge[w]) if (E.x != bef) {
		get_D(E.x, w);
		D[w] += D[E.x] + E.y;
	}
}
long long resX[212121];
void get_resX(long long w, long long bef, long long fromRoot) {
	long long sum = 0;
	for (xy E : edge[w]) if (E.x != bef) sum += D[E.x] + E.y;
	resX[w] = sum + fromRoot;
	for (xy E : edge[w]) if (E.x != bef) get_resX(E.x, w, fromRoot + sum - (D[E.x] + E.y) + E.z);
}
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_D(1, -1);
	get_resX(1, -1, 0);
	long long rootSum = 0, root = 1;
	for (i = 1; i <= n; i++) if (rootSum < resX[i])rootSum = resX[i], root = i;
	ans[1] = allsum - rootSum;
	long long q, x; scanf("%lld %lld", &q, &x);
	if (q == 1 && x == 1)printf("%lld", ans[1]);
	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:23:18: warning: unused variable 'j' [-Wunused-variable]
  long long n, i, j, allsum = 0; scanf("%lld", &n);
                  ^
designated_cities.cpp:32:25: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  long long rootSum = 0, root = 1;
                         ^~~~
designated_cities.cpp:23: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:25: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:35: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 8 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 5344 KB Output is correct
2 Correct 319 ms 28024 KB Output is correct
3 Correct 357 ms 38392 KB Output is correct
4 Correct 293 ms 26744 KB Output is correct
5 Correct 292 ms 27688 KB Output is correct
6 Correct 351 ms 29560 KB Output is correct
7 Correct 256 ms 26916 KB Output is correct
8 Correct 352 ms 38648 KB Output is correct
9 Correct 204 ms 26028 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 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 5344 KB Output is correct
2 Correct 319 ms 28024 KB Output is correct
3 Correct 357 ms 38392 KB Output is correct
4 Correct 293 ms 26744 KB Output is correct
5 Correct 292 ms 27688 KB Output is correct
6 Correct 351 ms 29560 KB Output is correct
7 Correct 256 ms 26916 KB Output is correct
8 Correct 352 ms 38648 KB Output is correct
9 Correct 204 ms 26028 KB Output is correct
10 Incorrect 8 ms 5368 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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