Submission #376171

#	Time	Username	Problem	Language	Result	Execution time	Memory
376171		casperwang	Designated Cities (JOI19_designated_cities)	C++14	33 / 100	1229 ms	105060 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

struct Edge {
	int to, val;
	Edge(int t, int v) {
		to = t, val = v;
	}
};

const int MAXN = 200000;
const int INF = 1e18;
int N, Q;
int a, b, c, d;
vector <int> path[MAXN+1];
vector <Edge> E;
pii dfs[MAXN+1];
int ord[MAXN*2+1];
int cnt;
int dis[MAXN+1];
bool vis[MAXN+1];
int cal;
int ans[MAXN+1];

class Seg {
	private:
		pii arr[MAXN*8+5];
		int tag[MAXN*8+5];
		void pull(int now) {
			arr[now] = max(arr[now*2], arr[now*2+1]);
		}
		void push(int now, int len) {
			if (!tag[now]) return;
			arr[now].ff += tag[now];
			if (len > 1) {
				tag[now*2  ] += tag[now];
				tag[now*2+1] += tag[now];
			}
			tag[now] = 0;
		}
	public:
		void build(int now=1, int l=1, int r=2*N) {
			tag[now] = 0;
			if (l == r) {
				arr[now] = pii(dis[ord[l]], ord[l]);
				return;
			}
			int mid = l + r >> 1;
			build(now*2  , l, mid);
			build(now*2+1,mid+1,r);
			pull(now);
		}
		void mdy(int ml, int mr, int k, int now=1, int l=1, int r=2*N) {
			push(now, r-l+1);
			if (ml <= l && r <= mr) {
				tag[now] += k;
				push(now, r-l+1);
				return;
			} else if (l > mr || r < ml) return;
			int mid = l + r >> 1;
			mdy(ml, mr, k, now*2  , l, mid);
			mdy(ml, mr, k, now*2+1,mid+1,r);
			pull(now);
		}
		pii qry() {
			return arr[1];
		}
} seg;

void dfs_init(int now, int par) {
	dfs[now].ff = ++cnt;
	ord[cnt] = now;
	for (int id : path[now]) {
		Edge e = E[id];
		if (e.to == par) continue;
		dis[e.to] = dis[now] + e.val;
		cal += e.val;
		dfs_init(e.to, now);
	}
	dfs[now].ss = ++cnt;
	ord[cnt] = now;
}

void dfs_1(int now, int par) {
	ans[1] = min(ans[1], cal);
	for (int id : path[now]) {
		Edge e = E[id], re = E[id^1];
		if (e.to == par) continue;
		cal += re.val - e.val;
		dfs_1(e.to, now);
		cal -= re.val - e.val;
	}
}

void dfs_2(int now, int par) {
	if (cal - seg.qry().ff < ans[2]) {
		ans[2] = cal - seg.qry().ff;
		a = now, b = seg.qry().ss;
	}
	for (int id : path[now]) {
		Edge e = E[id], re = E[id^1];
		if (e.to == par) continue;
		cal += re.val - e.val;
		seg.mdy(dfs[e.to].ff, dfs[e.to].ss, -e.val);
		seg.mdy(1, dfs[e.to].ff, re.val);
		seg.mdy(dfs[e.to].ss, 2*N, re.val);
		dfs_2(e.to, now);
		cal -= re.val - e.val;
		seg.mdy(dfs[e.to].ff, dfs[e.to].ss, e.val);
		seg.mdy(1, dfs[e.to].ff, -re.val);
		seg.mdy(dfs[e.to].ss, 2*N, -re.val);
	}
}

vector<int> line(int s, int t) {
	queue <int> nxt;
	vector <int> par(N+1);
	nxt.push(s);
	par[s] = s;
	while (nxt.size()) {
		int now = nxt.front();
		nxt.pop();
		for (int id : path[now]) {
			Edge e = E[id];
			if (!par[e.to]) {
				par[e.to] = now;
				nxt.push(e.to);
			}
		}
	}
	vector <int> res;
	while (par[t] != t) {
		res.pb(t);
		t = par[t];
	}
	res.pb(s);
	return res;
}

void dfs_dis(int now, int par) {
	dfs[now].ff = ++cnt;
	ord[cnt] = now;
	for (int id : path[now]) {
		Edge e = E[id];
		if (e.to == par || vis[e.to]) continue;
		dis[e.to] = dis[now] + e.val;
		dfs_dis(e.to, now);
	}
	dfs[now].ss = ++cnt;
	ord[cnt] = now;
}

void solve() {
	cal = 0;
	dfs_init(1, 0);
	dfs_1(1, 0);
	seg.build();
	dfs_2(1, 0);
	vector <int> v = line(a, b);
	for (int i : v) vis[i] = true, dis[i] = 0;
	cnt = 0;
	for (int i : v) dfs_dis(i, 0);
	seg.build();
	for (int i = 3; i <= N; i++) {
		ans[i] = ans[i-1] - seg.qry().ff;
		int nid = seg.qry().ss;
		if (vis[nid]) break;
		while (true) {
			int nxt = -1, c = 0;
			for (int id : path[nid]) {
				Edge e = E[id], re = E[id^1];
				if (dis[e.to] + re.val == dis[nid])
					nxt = e.to, c = re.val;
			}
			seg.mdy(dfs[nid].ff, dfs[nid].ss, -c);
			vis[nid] = true;
			if (nxt == -1 || vis[nxt]) break;
			nid = nxt;
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; i++) {
		cin >> a >> b >> c >> d;
		path[a].pb(E.size());
		E.pb(b, c);
		path[b].pb(E.size());
		E.pb(a, d);
		ans[i] = INF;
	}
	solve();
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> a;
		cout << ans[a] << '\n';
	}
}

Compilation message (stderr)

designated_cities.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
designated_cities.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    int mid = l + r >> 1;
      |              ~~^~~
designated_cities.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int, long long int)':
designated_cities.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |    int mid = l + r >> 1;
      |              ~~^~~

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