Submission #204073

#	Time	Username	Problem	Language	Result	Execution time	Memory
204073		ics0503	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	357 ms	38648 KiB

designated_cities

#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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44