oj.uz

Submission #554232

# Submission time Handle Problem Language Result Execution time Memory
554232 2022-04-28T03:43:32 Z amunduzbaev Reconstruction Project (JOI22_reconstruction) C++17
10 / 100
 3573 ms 164900 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--){
	    long long 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 0 ms 340 KB Output is correct
2 Correct 0 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 0 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 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 428 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 0 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 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 3132 ms 151736 KB Output is correct
21 Correct 1776 ms 151912 KB Output is correct
22 Correct 2657 ms 151740 KB Output is correct
23 Correct 2915 ms 151664 KB Output is correct
24 Correct 3026 ms 151880 KB Output is correct
25 Correct 3159 ms 151784 KB Output is correct
26 Correct 3160 ms 151748 KB Output is correct
27 Correct 3146 ms 146768 KB Output is correct
28 Incorrect 3078 ms 5192 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3559 ms 162916 KB Output is correct
5 Correct 3534 ms 162988 KB Output is correct
6 Correct 3573 ms 162720 KB Output is correct
7 Correct 816 ms 164812 KB Output is correct
8 Correct 777 ms 164900 KB Output is correct
9 Correct 748 ms 164884 KB Output is correct
10 Correct 3366 ms 162840 KB Output is correct
11 Correct 639 ms 164876 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 0 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 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 265 ms 14412 KB Output is correct
21 Correct 244 ms 14496 KB Output is correct
22 Correct 256 ms 14532 KB Output is correct
23 Correct 256 ms 14488 KB Output is correct
24 Correct 258 ms 14392 KB Output is correct
25 Correct 251 ms 14384 KB Output is correct
26 Correct 254 ms 13756 KB Output is correct
27 Incorrect 226 ms 12632 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 0 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 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 3132 ms 151736 KB Output is correct
21 Correct 1776 ms 151912 KB Output is correct
22 Correct 2657 ms 151740 KB Output is correct
23 Correct 2915 ms 151664 KB Output is correct
24 Correct 3026 ms 151880 KB Output is correct
25 Correct 3159 ms 151784 KB Output is correct
26 Correct 3160 ms 151748 KB Output is correct
27 Correct 3146 ms 146768 KB Output is correct
28 Incorrect 3078 ms 5192 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 0 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 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 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 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 3132 ms 151736 KB Output is correct
21 Correct 1776 ms 151912 KB Output is correct
22 Correct 2657 ms 151740 KB Output is correct
23 Correct 2915 ms 151664 KB Output is correct
24 Correct 3026 ms 151880 KB Output is correct
25 Correct 3159 ms 151784 KB Output is correct
26 Correct 3160 ms 151748 KB Output is correct
27 Correct 3146 ms 146768 KB Output is correct
28 Incorrect 3078 ms 5192 KB Output isn't correct
29 Halted 0 ms 0 KB -