Submission #376172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376172	2021-03-11T03:12:32 Z	casperwang	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1294 ms	102228 KB

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]) {
			ans[i] = 0;
			continue;
		}
		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

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

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30060 KB	Output is correct
2	Correct	18 ms	30188 KB	Output is correct
3	Correct	18 ms	30188 KB	Output is correct
4	Correct	18 ms	30188 KB	Output is correct
5	Correct	20 ms	30188 KB	Output is correct
6	Correct	18 ms	30188 KB	Output is correct
7	Correct	18 ms	30188 KB	Output is correct
8	Correct	18 ms	30188 KB	Output is correct
9	Correct	18 ms	30188 KB	Output is correct
10	Correct	18 ms	30188 KB	Output is correct
11	Correct	18 ms	30188 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	30060 KB	Output is correct
2	Correct	1216 ms	63432 KB	Output is correct
3	Correct	1145 ms	93968 KB	Output is correct
4	Correct	1174 ms	63432 KB	Output is correct
5	Correct	1180 ms	63560 KB	Output is correct
6	Correct	1205 ms	67656 KB	Output is correct
7	Correct	1089 ms	64200 KB	Output is correct
8	Correct	1138 ms	94920 KB	Output is correct
9	Correct	981 ms	65480 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30060 KB	Output is correct
2	Correct	1210 ms	63320 KB	Output is correct
3	Correct	1135 ms	98888 KB	Output is correct
4	Correct	1157 ms	63304 KB	Output is correct
5	Correct	1181 ms	63688 KB	Output is correct
6	Correct	1197 ms	68288 KB	Output is correct
7	Correct	990 ms	65224 KB	Output is correct
8	Correct	1172 ms	83144 KB	Output is correct
9	Correct	944 ms	65612 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30060 KB	Output is correct
2	Correct	18 ms	30188 KB	Output is correct
3	Correct	18 ms	30188 KB	Output is correct
4	Correct	18 ms	30188 KB	Output is correct
5	Correct	20 ms	30188 KB	Output is correct
6	Correct	18 ms	30188 KB	Output is correct
7	Correct	18 ms	30188 KB	Output is correct
8	Correct	18 ms	30188 KB	Output is correct
9	Correct	18 ms	30188 KB	Output is correct
10	Correct	18 ms	30188 KB	Output is correct
11	Correct	18 ms	30188 KB	Output is correct
12	Correct	18 ms	30060 KB	Output is correct
13	Correct	23 ms	30572 KB	Output is correct
14	Correct	23 ms	30700 KB	Output is correct
15	Correct	23 ms	30572 KB	Output is correct
16	Correct	23 ms	30572 KB	Output is correct
17	Correct	23 ms	30572 KB	Output is correct
18	Correct	23 ms	30572 KB	Output is correct
19	Correct	23 ms	30572 KB	Output is correct
20	Correct	23 ms	30572 KB	Output is correct
21	Correct	23 ms	30572 KB	Output is correct
22	Correct	23 ms	30572 KB	Output is correct
23	Correct	23 ms	30572 KB	Output is correct
24	Correct	23 ms	30572 KB	Output is correct
25	Correct	23 ms	30828 KB	Output is correct
26	Correct	23 ms	30572 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	30060 KB	Output is correct
2	Correct	1216 ms	63432 KB	Output is correct
3	Correct	1145 ms	93968 KB	Output is correct
4	Correct	1174 ms	63432 KB	Output is correct
5	Correct	1180 ms	63560 KB	Output is correct
6	Correct	1205 ms	67656 KB	Output is correct
7	Correct	1089 ms	64200 KB	Output is correct
8	Correct	1138 ms	94920 KB	Output is correct
9	Correct	981 ms	65480 KB	Output is correct
10	Correct	18 ms	30060 KB	Output is correct
11	Correct	1210 ms	63320 KB	Output is correct
12	Correct	1135 ms	98888 KB	Output is correct
13	Correct	1157 ms	63304 KB	Output is correct
14	Correct	1181 ms	63688 KB	Output is correct
15	Correct	1197 ms	68288 KB	Output is correct
16	Correct	990 ms	65224 KB	Output is correct
17	Correct	1172 ms	83144 KB	Output is correct
18	Correct	944 ms	65612 KB	Output is correct
19	Correct	17 ms	30060 KB	Output is correct
20	Correct	1204 ms	63320 KB	Output is correct
21	Correct	1138 ms	98972 KB	Output is correct
22	Correct	1185 ms	63580 KB	Output is correct
23	Correct	1215 ms	63432 KB	Output is correct
24	Correct	1198 ms	63432 KB	Output is correct
25	Correct	1207 ms	63320 KB	Output is correct
26	Correct	1199 ms	63332 KB	Output is correct
27	Correct	1191 ms	63556 KB	Output is correct
28	Correct	1205 ms	67528 KB	Output is correct
29	Correct	1251 ms	63648 KB	Output is correct
30	Correct	1234 ms	63980 KB	Output is correct
31	Correct	1103 ms	64936 KB	Output is correct
32	Correct	1214 ms	84312 KB	Output is correct
33	Correct	1010 ms	65868 KB	Output is correct

Subtask #6

44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30060 KB	Output is correct
2	Correct	18 ms	30188 KB	Output is correct
3	Correct	18 ms	30188 KB	Output is correct
4	Correct	18 ms	30188 KB	Output is correct
5	Correct	20 ms	30188 KB	Output is correct
6	Correct	18 ms	30188 KB	Output is correct
7	Correct	18 ms	30188 KB	Output is correct
8	Correct	18 ms	30188 KB	Output is correct
9	Correct	18 ms	30188 KB	Output is correct
10	Correct	18 ms	30188 KB	Output is correct
11	Correct	18 ms	30188 KB	Output is correct
12	Correct	17 ms	30060 KB	Output is correct
13	Correct	1216 ms	63432 KB	Output is correct
14	Correct	1145 ms	93968 KB	Output is correct
15	Correct	1174 ms	63432 KB	Output is correct
16	Correct	1180 ms	63560 KB	Output is correct
17	Correct	1205 ms	67656 KB	Output is correct
18	Correct	1089 ms	64200 KB	Output is correct
19	Correct	1138 ms	94920 KB	Output is correct
20	Correct	981 ms	65480 KB	Output is correct
21	Correct	18 ms	30060 KB	Output is correct
22	Correct	1210 ms	63320 KB	Output is correct
23	Correct	1135 ms	98888 KB	Output is correct
24	Correct	1157 ms	63304 KB	Output is correct
25	Correct	1181 ms	63688 KB	Output is correct
26	Correct	1197 ms	68288 KB	Output is correct
27	Correct	990 ms	65224 KB	Output is correct
28	Correct	1172 ms	83144 KB	Output is correct
29	Correct	944 ms	65612 KB	Output is correct
30	Correct	18 ms	30060 KB	Output is correct
31	Correct	23 ms	30572 KB	Output is correct
32	Correct	23 ms	30700 KB	Output is correct
33	Correct	23 ms	30572 KB	Output is correct
34	Correct	23 ms	30572 KB	Output is correct
35	Correct	23 ms	30572 KB	Output is correct
36	Correct	23 ms	30572 KB	Output is correct
37	Correct	23 ms	30572 KB	Output is correct
38	Correct	23 ms	30572 KB	Output is correct
39	Correct	23 ms	30572 KB	Output is correct
40	Correct	23 ms	30572 KB	Output is correct
41	Correct	23 ms	30572 KB	Output is correct
42	Correct	23 ms	30572 KB	Output is correct
43	Correct	23 ms	30828 KB	Output is correct
44	Correct	23 ms	30572 KB	Output is correct
45	Correct	17 ms	30060 KB	Output is correct
46	Correct	1204 ms	63320 KB	Output is correct
47	Correct	1138 ms	98972 KB	Output is correct
48	Correct	1185 ms	63580 KB	Output is correct
49	Correct	1215 ms	63432 KB	Output is correct
50	Correct	1198 ms	63432 KB	Output is correct
51	Correct	1207 ms	63320 KB	Output is correct
52	Correct	1199 ms	63332 KB	Output is correct
53	Correct	1191 ms	63556 KB	Output is correct
54	Correct	1205 ms	67528 KB	Output is correct
55	Correct	1251 ms	63648 KB	Output is correct
56	Correct	1234 ms	63980 KB	Output is correct
57	Correct	1103 ms	64936 KB	Output is correct
58	Correct	1214 ms	84312 KB	Output is correct
59	Correct	1010 ms	65868 KB	Output is correct
60	Correct	18 ms	30060 KB	Output is correct
61	Correct	1294 ms	72136 KB	Output is correct
62	Correct	1196 ms	102228 KB	Output is correct
63	Correct	1214 ms	70856 KB	Output is correct
64	Correct	1252 ms	72240 KB	Output is correct
65	Correct	1237 ms	71084 KB	Output is correct
66	Correct	1228 ms	72264 KB	Output is correct
67	Correct	1267 ms	70864 KB	Output is correct
68	Correct	1234 ms	72532 KB	Output is correct
69	Correct	1232 ms	76236 KB	Output is correct
70	Correct	1263 ms	72448 KB	Output is correct
71	Correct	1211 ms	71880 KB	Output is correct
72	Correct	1137 ms	74056 KB	Output is correct
73	Correct	1218 ms	89916 KB	Output is correct
74	Correct	993 ms	75848 KB	Output is correct