Submission #132772

#	Time	Username	Problem	Language	Result	Execution time	Memory
132772		imyujin	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	863 ms	42392 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define fi first
#define se second
#define mp make_pair

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<lint, int> pli;

vector<piii> ed[MAXN];
int par[MAXN], pare[MAXN];
bool chk[MAXN];
lint ans[MAXN], dis[MAXN];
int dfsord[MAXN], dfsr[MAXN], dfsver[MAXN], dfsn;
pli seg[4 * MAXN];
lint lazy[4 * MAXN];

lint gsum(int x) {
	lint ans = 0ll;
	for(auto a : ed[x]) if(a.se != par[x]) {
		ans += a.fi.se;
		par[a.se] = x;
		ans += gsum(a.se);
	}
	//if(x == 1) printf("gsum(1) = %lld\n", ans);
	return ans;
}

void dfs(int x, lint s) {
	ans[0] = max(ans[0], s);
	for(auto a : ed[x]) if(a.se != par[x]) 
		dfs(a.se, s + a.fi.fi - a.fi.se);
}

void gdis(int x) {
	for(auto a : ed[x]) if(a.se != par[x]) {
		par[a.se] = x;
		dis[a.se] = dis[x] + a.fi.fi;
		gdis(a.se);
	}
}

void preord(int x) {
	dfsord[x] = ++dfsn;
	dfsver[dfsord[x]] = x;
	for(auto a : ed[x]) if(a.se != par[x]) {
		par[a.se] = x;
		preord(a.se);
	}
	dfsr[x] = dfsn;
}

void mkseg(int idx, int l, int r) {
	seg[idx] = mp(0ll, l);
	if(l < r) {
		int m = (l + r) / 2;
		mkseg(idx * 2, l, m);
		mkseg(idx * 2 + 1, m + 1, r);
	}
}

void updseg(int idx, int l, int r, int x, int y, int z) {
	if(x <= l && r <= y) {
		seg[idx].fi += z;
		lazy[idx] += z;
	}
	else if(l <= y && x <= r) {
		int m = (l + r) / 2;
		updseg(idx * 2, l, m, x, y, z);
		updseg(idx * 2 + 1, m + 1, r, x, y, z);
		seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
		seg[idx].fi += lazy[idx];
	}
}

int main() {
	int N, Q;
	int A, B, C, D;
	int u = 1;
	lint sum = 0ll;

	scanf("%d", &N);
	for(int i = 0; i < N - 1; i++) {
		scanf("%d%d%d%d", &A, &B, &C, &D);
		ed[A].push_back(mp(mp(C, D), B));
		ed[B].push_back(mp(mp(D, C), A));
		sum += C + D;
	}

	dfs(1, gsum(1));
	gdis(1);
	for(int i = 2; i <= N; i++) if(dis[i] > dis[u]) u = i;
	par[u] = dis[u] = 0;
	preord(u);
	//printf("u = %d\n", u);

	//printf("ans[0] = %lld\n", ans[0]);

	mkseg(1, 1, N);
	for(int i = 1; i <= N; i++) if(i != u) {
		int e;
		for(e = 0; ed[i][e].se != par[i]; e++);
		pare[i] = ed[i][e].fi.se;
		updseg(1, 1, N, dfsord[i], dfsr[i], pare[i]);
	}

	par[u] = 0;
	ans[1] = gsum(u);
	chk[u] = true;
	for(int i = 2; i <= N; i++) {
		ans[i] = ans[i - 1] + seg[1].fi;
		for(int t = dfsver[seg[1].se]; !chk[t]; t = par[t]) {
			//printf("i = %d, t = %d\n", i, t);
			updseg(1, 1, N, dfsord[t], dfsr[t], -pare[t]);
			chk[t] = true;
		}
	}

	scanf("%d", &Q);
	while(Q--) {
		scanf("%d", &A);
		printf("%lld\n", sum - ans[A == 1 ? 0 : A]);
	}
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A, &B, &C, &D);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
designated_cities.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A);
   ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44