oj.uz

Submission #537643

# Submission time Handle Problem Language Result Execution time Memory
537643 2022-03-15T10:31:34 Z hmm789 Paths (RMI21_paths) C++14
48 / 100
 600 ms 407264 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 15 ms 9048 KB Output is correct
4 Correct 19 ms 8992 KB Output is correct
5 Correct 17 ms 8996 KB Output is correct
6 Correct 21 ms 9076 KB Output is correct
7 Correct 18 ms 9020 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 15 ms 9048 KB Output is correct
4 Correct 19 ms 8992 KB Output is correct
5 Correct 17 ms 8996 KB Output is correct
6 Correct 21 ms 9076 KB Output is correct
7 Correct 18 ms 9020 KB Output is correct
8 Correct 353 ms 159384 KB Output is correct
9 Correct 426 ms 159304 KB Output is correct
10 Correct 412 ms 159344 KB Output is correct
11 Correct 283 ms 159300 KB Output is correct
12 Correct 323 ms 159292 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 15 ms 9048 KB Output is correct
4 Correct 19 ms 8992 KB Output is correct
5 Correct 17 ms 8996 KB Output is correct
6 Correct 21 ms 9076 KB Output is correct
7 Correct 18 ms 9020 KB Output is correct
8 Correct 353 ms 159384 KB Output is correct
9 Correct 426 ms 159304 KB Output is correct
10 Correct 412 ms 159344 KB Output is correct
11 Correct 283 ms 159300 KB Output is correct
12 Correct 323 ms 159292 KB Output is correct
13 Execution timed out 1108 ms 407264 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10936 KB Output is correct
2 Correct 85 ms 12240 KB Output is correct
3 Correct 65 ms 10592 KB Output is correct
4 Correct 71 ms 10692 KB Output is correct
5 Correct 77 ms 11720 KB Output is correct
6 Correct 68 ms 10588 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 15 ms 9048 KB Output is correct
4 Correct 19 ms 8992 KB Output is correct
5 Correct 17 ms 8996 KB Output is correct
6 Correct 21 ms 9076 KB Output is correct
7 Correct 18 ms 9020 KB Output is correct
8 Correct 353 ms 159384 KB Output is correct
9 Correct 426 ms 159304 KB Output is correct
10 Correct 412 ms 159344 KB Output is correct
11 Correct 283 ms 159300 KB Output is correct
12 Correct 323 ms 159292 KB Output is correct
13 Execution timed out 1108 ms 407264 KB Time limit exceeded
14 Halted 0 ms 0 KB -