Submission #376159

#	Time	Username	Problem	Language	Result	Execution time	Memory
376159		casperwang	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	972 ms	82504 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];
int ans[MAXN+1];
int cal;

class Seg {
	private:
		int 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] += 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) {
			if (l == r) {
				arr[now] = dis[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);
		}
		int 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) {
	ans[2] = min(ans[2], cal - seg.qry());
	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);
	}
}

void solve() {
	cal = 0;
	dfs_init(1, 0);
	dfs_1(1, 0);
	seg.build();
	dfs_2(1, 0);
}

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:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |    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:67:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    int mid = l + r >> 1;
      |              ~~^~~

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