oj.uz

Submission #554231

# Submission time Handle Problem Language Result Execution time Memory
554231 2022-04-28T03:36:46 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
10 / 100
 3558 ms 165704 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
const int N = 1e5 + 5;
const int M = 1e9 + 5;
const int MAXN = 505;

struct ST{
	long long tree[N * 60];
	int ch[N * 60][2], last;
	ST(){
		last = 0;
	}
	
	int bala(int x, int t){
		if(!ch[x][t]){
			ch[x][t] = ++last;
		}
		return ch[x][t];
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = M, int x = 0){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, bala(x, 0));
		add(l, r, v, m+1, rx, bala(x, 1));
	}
	
	long long get(int i, int lx = 0, int rx = M, int x = 0){
		if(lx == rx) return tree[x];
		int m = (lx + rx) >> 1;
		if(i <= m && ch[x][0]) return tree[x] + get(i, lx, m, ch[x][0]);
		if(m < i && ch[x][1]) return tree[x] + get(i, m+1, rx, ch[x][1]);
		return tree[x];
	}
}tree, cnt;

int a[N], b[N], w[N];
int l[N], r[N];
vector<int> edges[MAXN];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<int> p(m);
	for(int i=0;i<m;i++){ p[i] = i;
		cin>>a[i]>>b[i]>>w[i];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (w[i] > w[j]);
	});
	
	auto er = [&](vector<int>& a, int v){
		for(int i=0;i<(int)a.size();i++){
			if(a[i] == v){
				a.erase(a.begin() + i, a.begin() + i + 1);
				return;
			}
		}
	};
	
	w[m] = -1;
	for(auto i : p){
		int in = -1, R = w[i];
        function<void(int, int, int)> dfs = [&](int u, int ed, int p){
	        if(u == b[i]){
        		in = ed;
        	}
        	
        	for(auto j : edges[u]){
        		int x = a[j] ^ b[j] ^ u;
        		if(x == p) continue;
        		int tmp = ed;
        		if(w[j] > w[ed]) tmp = j;
        		else if(w[j] == w[ed] && j > ed) tmp = j;
        		dfs(x, tmp, u);
        	}
	    };
	    
		dfs(a[i], m, a[i]);
		if(in == -1){
			R = M;
		} else {
		    R = (w[i] + w[in]) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) R--;
			er(edges[a[in]], in);
			er(edges[b[in]], in);
		} R = max(R, w[i]);
		
		r[i] = R;
		tree.add(w[i], R, -w[i]);
		cnt.add(w[i], R, 1);
		edges[a[i]].push_back(i);
		edges[b[i]].push_back(i);
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (w[i] < w[j]);
	});
	
	for(int i=1;i<=n;i++) edges[i].clear();
	w[m] = M;
	for(auto i : p){
		int in = -1, L = w[i];
        function<void(int, int, int)> dfs = [&](int u, int ed, int p){
	        if(u == b[i]){
        		in = ed;
        	}
        	
        	for(auto j : edges[u]){
        		int x = a[j] ^ b[j] ^ u;
        		if(x == p) continue;
        		int tmp = ed;
        		if(w[j] < w[ed]) tmp = j;
        		else if(w[j] == w[ed] && j > ed) tmp = j;
        		dfs(x, tmp, u);
        	}
	    };
	    
		dfs(a[i], m, a[i]);
		if(in == -1){
			L = 0;
		} else {
		    L = (w[i] + w[in] + 1) / 2;
			if((w[in]&1) == (w[i]&1) && in < i) L++;
			er(edges[a[in]], in);
			er(edges[b[in]], in);
		} L = min(L, w[i]);
		
		l[i] = L;
		tree.add(L, w[i], w[i]);
		cnt.add(L, w[i], -1);
		edges[a[i]].push_back(i);
		edges[b[i]].push_back(i);
	}
	
	int q; cin>>q;
	while(q--){
	    int x; cin>>x;
	    cout<<tree.get(x) + cnt.get(x) * x<<"\n";
	}
}

/*



2 4 15
1 3 13
1 5 11
1 2 8
2 3 7
3 4 6
3 5 6
1 4 5
1 5 3
4 5 2

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
2
6
3

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 3135 ms 152892 KB Output is correct
21 Correct 1754 ms 151784 KB Output is correct
22 Correct 2684 ms 151868 KB Output is correct
23 Correct 2891 ms 151660 KB Output is correct
24 Correct 2994 ms 151772 KB Output is correct
25 Correct 3000 ms 151784 KB Output is correct
26 Correct 3080 ms 152708 KB Output is correct
27 Correct 3116 ms 147472 KB Output is correct
28 Incorrect 3003 ms 5960 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3558 ms 164176 KB Output is correct
5 Correct 3490 ms 163700 KB Output is correct
6 Correct 3488 ms 163640 KB Output is correct
7 Correct 821 ms 165704 KB Output is correct
8 Correct 774 ms 165552 KB Output is correct
9 Correct 747 ms 165452 KB Output is correct
10 Correct 3363 ms 163484 KB Output is correct
11 Correct 619 ms 165436 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 244 ms 15384 KB Output is correct
21 Correct 247 ms 15600 KB Output is correct
22 Correct 241 ms 15464 KB Output is correct
23 Correct 241 ms 15300 KB Output is correct
24 Correct 245 ms 15260 KB Output is correct
25 Correct 251 ms 15424 KB Output is correct
26 Correct 234 ms 14780 KB Output is correct
27 Incorrect 214 ms 13516 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 3135 ms 152892 KB Output is correct
21 Correct 1754 ms 151784 KB Output is correct
22 Correct 2684 ms 151868 KB Output is correct
23 Correct 2891 ms 151660 KB Output is correct
24 Correct 2994 ms 151772 KB Output is correct
25 Correct 3000 ms 151784 KB Output is correct
26 Correct 3080 ms 152708 KB Output is correct
27 Correct 3116 ms 147472 KB Output is correct
28 Incorrect 3003 ms 5960 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 352 KB Output is correct
20 Correct 3135 ms 152892 KB Output is correct
21 Correct 1754 ms 151784 KB Output is correct
22 Correct 2684 ms 151868 KB Output is correct
23 Correct 2891 ms 151660 KB Output is correct
24 Correct 2994 ms 151772 KB Output is correct
25 Correct 3000 ms 151784 KB Output is correct
26 Correct 3080 ms 152708 KB Output is correct
27 Correct 3116 ms 147472 KB Output is correct
28 Incorrect 3003 ms 5960 KB Output isn't correct
29 Halted 0 ms 0 KB -