Submission #204074

#	Time	Username	Problem	Language	Result	Execution time	Memory
204074		ics0503	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	456 ms	66344 KiB

designated_cities

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

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