oj.uz

Submission #376171

# Submission time Handle Problem Language Result Execution time Memory
376171 2021-03-11T03:11:24 Z casperwang Designated Cities (JOI19_designated_cities) C++14
33 / 100
 1229 ms 105060 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30060 KB Output is correct
2 Incorrect 18 ms 30188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30188 KB Output is correct
2 Correct 1229 ms 63336 KB Output is correct
3 Correct 1135 ms 93896 KB Output is correct
4 Correct 1163 ms 63176 KB Output is correct
5 Correct 1167 ms 63484 KB Output is correct
6 Correct 1179 ms 67400 KB Output is correct
7 Correct 1080 ms 63964 KB Output is correct
8 Correct 1147 ms 94348 KB Output is correct
9 Correct 950 ms 65208 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30188 KB Output is correct
2 Correct 1201 ms 63216 KB Output is correct
3 Correct 1143 ms 98296 KB Output is correct
4 Correct 1211 ms 63268 KB Output is correct
5 Correct 1186 ms 63432 KB Output is correct
6 Correct 1172 ms 67912 KB Output is correct
7 Correct 985 ms 64960 KB Output is correct
8 Correct 1166 ms 82588 KB Output is correct
9 Correct 943 ms 65228 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30060 KB Output is correct
2 Incorrect 18 ms 30188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30188 KB Output is correct
2 Correct 1229 ms 63336 KB Output is correct
3 Correct 1135 ms 93896 KB Output is correct
4 Correct 1163 ms 63176 KB Output is correct
5 Correct 1167 ms 63484 KB Output is correct
6 Correct 1179 ms 67400 KB Output is correct
7 Correct 1080 ms 63964 KB Output is correct
8 Correct 1147 ms 94348 KB Output is correct
9 Correct 950 ms 65208 KB Output is correct
10 Correct 18 ms 30188 KB Output is correct
11 Correct 1201 ms 63216 KB Output is correct
12 Correct 1143 ms 98296 KB Output is correct
13 Correct 1211 ms 63268 KB Output is correct
14 Correct 1186 ms 63432 KB Output is correct
15 Correct 1172 ms 67912 KB Output is correct
16 Correct 985 ms 64960 KB Output is correct
17 Correct 1166 ms 82588 KB Output is correct
18 Correct 943 ms 65228 KB Output is correct
19 Correct 18 ms 30060 KB Output is correct
20 Correct 1193 ms 63176 KB Output is correct
21 Correct 1155 ms 105060 KB Output is correct
22 Correct 1175 ms 68172 KB Output is correct
23 Correct 1212 ms 69692 KB Output is correct
24 Correct 1213 ms 68424 KB Output is correct
25 Correct 1208 ms 69464 KB Output is correct
26 Correct 1198 ms 68564 KB Output is correct
27 Correct 1191 ms 69812 KB Output is correct
28 Correct 1219 ms 73728 KB Output is correct
29 Correct 1227 ms 70060 KB Output is correct
30 Correct 1153 ms 69064 KB Output is correct
31 Correct 1060 ms 70856 KB Output is correct
32 Correct 1158 ms 90184 KB Output is correct
33 Correct 951 ms 71732 KB Output is correct

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30060 KB Output is correct
2 Incorrect 18 ms 30188 KB Output isn't correct
3 Halted 0 ms 0 KB -