oj.uz

Submission #537614

# Submission time Handle Problem Language Result Execution time Memory
537614 2022-03-15T09:45:00 Z hmm789 Paths (RMI21_paths) C++14
36 / 100
 600 ms 367884 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];
			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 9044 KB Output is correct
4 Correct 16 ms 9052 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 19 ms 9048 KB Output is correct
7 Correct 16 ms 8968 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 9044 KB Output is correct
4 Correct 16 ms 9052 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 19 ms 9048 KB Output is correct
7 Correct 16 ms 8968 KB Output is correct
8 Correct 371 ms 159300 KB Output is correct
9 Correct 413 ms 159500 KB Output is correct
10 Correct 411 ms 159396 KB Output is correct
11 Correct 291 ms 159300 KB Output is correct
12 Correct 332 ms 159432 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 9044 KB Output is correct
4 Correct 16 ms 9052 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 19 ms 9048 KB Output is correct
7 Correct 16 ms 8968 KB Output is correct
8 Correct 371 ms 159300 KB Output is correct
9 Correct 413 ms 159500 KB Output is correct
10 Correct 411 ms 159396 KB Output is correct
11 Correct 291 ms 159300 KB Output is correct
12 Correct 332 ms 159432 KB Output is correct
13 Execution timed out 1118 ms 367884 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 1114 ms 356320 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 9044 KB Output is correct
4 Correct 16 ms 9052 KB Output is correct
5 Correct 12 ms 9044 KB Output is correct
6 Correct 19 ms 9048 KB Output is correct
7 Correct 16 ms 8968 KB Output is correct
8 Correct 371 ms 159300 KB Output is correct
9 Correct 413 ms 159500 KB Output is correct
10 Correct 411 ms 159396 KB Output is correct
11 Correct 291 ms 159300 KB Output is correct
12 Correct 332 ms 159432 KB Output is correct
13 Execution timed out 1118 ms 367884 KB Time limit exceeded
14 Halted 0 ms 0 KB -