oj.uz

Submission #554229

# Submission time Handle Problem Language Result Execution time Memory
554229 2022-04-28T03:35:15 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
10 / 100
 2754 ms 165916 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;
        		return;
        	}
        	
        	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);
        		if(~in) return;
        	}
	    };
	    
		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 352 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 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 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 356 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 352 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 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 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 356 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2479 ms 152936 KB Output is correct
21 Correct 1404 ms 151752 KB Output is correct
22 Correct 2088 ms 151796 KB Output is correct
23 Correct 2325 ms 151956 KB Output is correct
24 Correct 2312 ms 151816 KB Output is correct
25 Correct 2427 ms 151692 KB Output is correct
26 Correct 2494 ms 153368 KB Output is correct
27 Correct 2754 ms 148452 KB Output is correct
28 Incorrect 2373 ms 6792 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 352 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2508 ms 165636 KB Output is correct
5 Correct 2483 ms 164308 KB Output is correct
6 Correct 2474 ms 163788 KB Output is correct
7 Correct 798 ms 165428 KB Output is correct
8 Correct 777 ms 165916 KB Output is correct
9 Correct 743 ms 165728 KB Output is correct
10 Correct 2349 ms 163572 KB Output is correct
11 Correct 615 ms 165652 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 352 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 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 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 356 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 255 ms 15136 KB Output is correct
21 Correct 258 ms 15312 KB Output is correct
22 Correct 254 ms 15408 KB Output is correct
23 Correct 259 ms 15180 KB Output is correct
24 Correct 254 ms 15180 KB Output is correct
25 Correct 245 ms 15140 KB Output is correct
26 Correct 250 ms 14720 KB Output is correct
27 Incorrect 231 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 352 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 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 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 356 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2479 ms 152936 KB Output is correct
21 Correct 1404 ms 151752 KB Output is correct
22 Correct 2088 ms 151796 KB Output is correct
23 Correct 2325 ms 151956 KB Output is correct
24 Correct 2312 ms 151816 KB Output is correct
25 Correct 2427 ms 151692 KB Output is correct
26 Correct 2494 ms 153368 KB Output is correct
27 Correct 2754 ms 148452 KB Output is correct
28 Incorrect 2373 ms 6792 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 352 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 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 416 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 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 356 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2479 ms 152936 KB Output is correct
21 Correct 1404 ms 151752 KB Output is correct
22 Correct 2088 ms 151796 KB Output is correct
23 Correct 2325 ms 151956 KB Output is correct
24 Correct 2312 ms 151816 KB Output is correct
25 Correct 2427 ms 151692 KB Output is correct
26 Correct 2494 ms 153368 KB Output is correct
27 Correct 2754 ms 148452 KB Output is correct
28 Incorrect 2373 ms 6792 KB Output isn't correct
29 Halted 0 ms 0 KB -