Submission #132763

#	Time	Username	Problem	Language	Result	Execution time	Memory
132763		youngyojun	Designated Cities (JOI19_designated_cities)	C++11	100 / 100	855 ms	51704 KiB

designated_cities

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;

const int MAXN = 200055;

struct SEG {
	ll dmx[MAXN*3], ds[MAXN*3];
	int di[MAXN*3];

	void init(int i, int s, int e) {
		if(s == e) {
			di[i] = s;
			return;
		}
		int m = (s+e) >> 1;
		init(i<<1, s, m);
		init(i<<1|1, m+1, e);
		di[i] = s;
	}
	void upd(int i, int s, int e, int p, int q, ll r) {
		if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			ds[i] += r;
			dmx[i] += r;
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		int j = dmx[i<<1] < dmx[i<<1|1] ? (i<<1|1) : (i<<1);
		dmx[i] = dmx[j] + ds[i];
		di[i] = di[j];
	}
	int get() { return di[1]; }
} seg;

vector<int> G[MAXN];
ll dl[MAXN];
int prt[MAXN], prte[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN], rfo[MAXN];
bitset<MAXN> chk;

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];

ll Ans[MAXN], Sum;
int N, Q, Rt;

void goup(int i, ll &sum) {
	for(; !chk[i]; i = prt[i]) {
		sum += C[prte[i]];
		seg.upd(1, 1, N, dfo[i], dfo[i]+cnt[i]-1, -C[prte[i]]);
		chk[i] = true;
	}
}

int getCost(int p, int e) { return p == A[e] ? C[e] : D[e]; }
void predfs(int i, int &c) {
	cnt[i] = 1; dfo[i] = ++c;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(v == prt[i]) continue;
		dep[v] = dep[i] + 1;
		prt[v] = i;
		prte[v] = e;
		dl[v] = dl[i] + getCost(i, e);
		predfs(v, c);
		cnt[i] += cnt[v];
	}
}
void predfs(int i) { int c = 0; predfs(i, c); }

void findRt() {
	predfs(1);
	Rt = int(max_element(dl+1, dl+N+1) - dl);
	prt[Rt] = 0; dl[Rt] = 0;
	predfs(Rt);
	for(int i = 1; i <= N; i++) rfo[dfo[i]] = i;
	for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) {
		swap(A[i], B[i]);
		swap(C[i], D[i]);
	}
}

void getAnsTwo() {
	ll sum = 0;
	seg.init(1, 1, N);
	chk[Rt] = true;
	for(int i = 1, v; i < N; i++) {
		sum += D[i];
		v = B[i];
		seg.upd(1, 1, N, dfo[v], dfo[v]+cnt[v]-1, C[i]);
	}
	for(int t = 2, i; t <= N; t++) {
		i = rfo[seg.get()];
		goup(i, sum);
		Ans[t] = sum;
	}
}

void dfsOne(int i, ll sum) {
	if(Ans[1] < sum) Ans[1] = sum;
	for(int e : G[i]) if(A[e] != prt[i])
		dfsOne(B[e], sum - D[e] + C[e]);
}

void getAnsOne() {
	predfs(1);
	for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) {
		swap(A[i], B[i]);
		swap(C[i], D[i]);
	}
	ll sum = 0;
	for(int i = 1; i < N; i++) sum += D[i];
	dfsOne(1, sum);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
		Sum += C[i] + D[i];
	}

	getAnsOne();
	findRt();
	getAnsTwo();

	cin >> Q;
	for(int a; Q--;) {
		cin >> a;
		printf("%lld\n", Sum - Ans[a]);
	}
	return 0;
}

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