oj.uz

Submission #537620

# Submission time Handle Problem Language Result Execution time Memory
537620 2022-03-15T09:56:27 Z hmm789 Paths (RMI21_paths) C++14
36 / 100
 600 ms 397796 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);
}

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));
	}
	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 2 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 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 13 ms 9060 KB Output is correct
4 Correct 17 ms 8948 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 18 ms 8948 KB Output is correct
7 Correct 16 ms 9036 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 13 ms 9060 KB Output is correct
4 Correct 17 ms 8948 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 18 ms 8948 KB Output is correct
7 Correct 16 ms 9036 KB Output is correct
8 Correct 350 ms 159336 KB Output is correct
9 Correct 427 ms 159368 KB Output is correct
10 Correct 417 ms 159316 KB Output is correct
11 Correct 286 ms 159288 KB Output is correct
12 Correct 341 ms 159296 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 13 ms 9060 KB Output is correct
4 Correct 17 ms 8948 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 18 ms 8948 KB Output is correct
7 Correct 16 ms 9036 KB Output is correct
8 Correct 350 ms 159336 KB Output is correct
9 Correct 427 ms 159368 KB Output is correct
10 Correct 417 ms 159316 KB Output is correct
11 Correct 286 ms 159288 KB Output is correct
12 Correct 341 ms 159296 KB Output is correct
13 Execution timed out 1109 ms 397796 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1112 ms 340528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 13 ms 9060 KB Output is correct
4 Correct 17 ms 8948 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 18 ms 8948 KB Output is correct
7 Correct 16 ms 9036 KB Output is correct
8 Correct 350 ms 159336 KB Output is correct
9 Correct 427 ms 159368 KB Output is correct
10 Correct 417 ms 159316 KB Output is correct
11 Correct 286 ms 159288 KB Output is correct
12 Correct 341 ms 159296 KB Output is correct
13 Execution timed out 1109 ms 397796 KB Time limit exceeded
14 Halted 0 ms 0 KB -