Submission #537643

#	Time	Username	Problem	Language	Result	Execution time	Memory
537643		hmm789	Paths (RMI21_paths)	C++14	48 / 100	1108 ms	407264 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 

struct node {
	int s, e, m, v, lz, idx;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e, v = 0, lz = 0, idx = s;
		m = (s+e)/2;
		if(s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void prop() {
		if(lz == 0) return;
		v += lz;
		if(s != e) {
			l->lz += lz;
			r->lz += lz;
		}
		lz = 0;
	}
	void update(int x, int y, int val) {
		if(x <= s && e <= y) {lz += val; return;}
		else if(x > m) r->update(x, y, val);
		else if(y <= m) l->update(x, y, val);
		else l->update(x, y, val), r->update(x, y, val);
		l->prop(), r->prop();
		if(l->v > r->v) {
			v = l->v;
			idx = l->idx;
		} else {
			v = r->v;
			idx = r->idx;
		}
	}
	pair<int, int> query(int x, int y) {
		if(x <= s && e <= y) return make_pair(v, idx);
		else if(x > m) return r->query(x, y);
		else if(y <= m) return l->query(x, y);
		else {
			pair<int, int> tmp = l->query(x, y);
			pair<int, int> tmp2 = r->query(x, y);
			if(tmp.first > tmp2.first) return tmp;
			else return tmp2;
		}
	}
} *root;
		
vector<pair<int, int>> adj[100000];
int pre[100000], vtx[100000], post[100000], par[100000], pard[100000], cur;
bool v[100000];

void dfs(int x, int p) {
	vtx[cur] = x;
	pre[x] = cur++;
	par[x] = p;
	for(auto i : adj[x]) if(i.first != p) {
		pard[i.first] = i.second;
		dfs(i.first, x);
	}
	post[x] = cur-1;
}

void dfs2(int x, int d, int p) {
	root->update(pre[x], pre[x], d);
	for(auto i : adj[x]) if(i.first != p) dfs2(i.first, d+i.second, x);
}

int dist[100000], dist2[100000];

void dfs3(int x, int d, int p) {
	dist[x] = d;
	for(auto i : adj[x]) if(i.first != p) dfs3(i.first, d+i.second, x);
}

void dfs4(int x, int d, int p, bool b) {
	if(b) dist[x] = d;
	else dist2[x] = d;
	for(auto i : adj[x]) if(i.first != p) dfs4(i.first, d+i.second, x, b);
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k, a, b, w, ans, curv;
	cin >> n >> k;
	for(int i = 0; i < n-1; i++) {
		cin >> a >> b >> w;
		a--; b--;
		adj[a].push_back(make_pair(b, w));
		adj[b].push_back(make_pair(a, w));
	}
	if(k == 1) {
		dfs3(0, 0, -1);
		int far = 0, far2 = 0;
		for(int i = 0; i < n; i++) if(dist[i] > dist[far]) far = i;
		dfs3(far, 0, -1);
		for(int i = 0; i < n; i++) if(dist[i] > dist[far2]) far2 = i;
		dfs4(far, 0, -1, 0);
		dfs4(far2, 0, -1, 1);
		for(int i = 0; i < n; i++) {
			cout << max(dist[i], dist2[i]) << '\n';
		}
		return 0;
	}
	for(int i = 0; i < n; i++) {
		cur = 0;
		dfs(i, -1);
		par[i] = -1;
		root = new node(0, n-1);
		dfs2(i, 0, -1);
		ans = 0;
		if(k != 1) memset(v, 0, sizeof(v));
		for(int j = 0; j < k; j++) {
			pair<int, int> tmp = root->query(0, n-1);
			ans += tmp.first;
			curv = vtx[tmp.second];
			if(k != 1) {
				while(curv != -1 && !v[curv]) {
					v[curv] = 1;
					root->update(pre[curv], post[curv], -pard[curv]);
					curv = par[curv];
				}
			}
		}
		cout << ans << '\n';
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32