oj.uz

Submission #537617

# Submission time Handle Problem Language Result Execution time Memory
537617 2022-03-15T09:54:47 Z hmm789 Paths (RMI21_paths) C++14
36 / 100
 600 ms 401100 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;
		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 14 ms 8980 KB Output is correct
4 Correct 15 ms 8936 KB Output is correct
5 Correct 12 ms 9060 KB Output is correct
6 Correct 17 ms 9044 KB Output is correct
7 Correct 15 ms 8980 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 14 ms 8980 KB Output is correct
4 Correct 15 ms 8936 KB Output is correct
5 Correct 12 ms 9060 KB Output is correct
6 Correct 17 ms 9044 KB Output is correct
7 Correct 15 ms 8980 KB Output is correct
8 Correct 355 ms 159260 KB Output is correct
9 Correct 408 ms 159400 KB Output is correct
10 Correct 407 ms 159308 KB Output is correct
11 Correct 280 ms 159344 KB Output is correct
12 Correct 342 ms 159244 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 14 ms 8980 KB Output is correct
4 Correct 15 ms 8936 KB Output is correct
5 Correct 12 ms 9060 KB Output is correct
6 Correct 17 ms 9044 KB Output is correct
7 Correct 15 ms 8980 KB Output is correct
8 Correct 355 ms 159260 KB Output is correct
9 Correct 408 ms 159400 KB Output is correct
10 Correct 407 ms 159308 KB Output is correct
11 Correct 280 ms 159344 KB Output is correct
12 Correct 342 ms 159244 KB Output is correct
13 Execution timed out 1115 ms 401100 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 1106 ms 372280 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 14 ms 8980 KB Output is correct
4 Correct 15 ms 8936 KB Output is correct
5 Correct 12 ms 9060 KB Output is correct
6 Correct 17 ms 9044 KB Output is correct
7 Correct 15 ms 8980 KB Output is correct
8 Correct 355 ms 159260 KB Output is correct
9 Correct 408 ms 159400 KB Output is correct
10 Correct 407 ms 159308 KB Output is correct
11 Correct 280 ms 159344 KB Output is correct
12 Correct 342 ms 159244 KB Output is correct
13 Execution timed out 1115 ms 401100 KB Time limit exceeded
14 Halted 0 ms 0 KB -