oj.uz

Submission #554289

# Submission time Handle Problem Language Result Execution time Memory
554289 2022-04-28T06:32:33 Z Arvin Reconstruction Project (JOI22_reconstruction) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxN = 505;

struct DSU {
	int parent[maxN], sz[maxN];
	
	void reset(){
		for(int x=0;x<maxN;x++){
			parent[x] = x;
			sz[x] = 1;
		}
	}
	
	int getParent(int x){
		if(parent[x] == x) return x;
		return parent[x] = getParent(parent[x]);
	}
	
	bool merge(int x, int y){
		int a = getParent(x);
		int b = getParent(y);
		
		if(a != b){
			if(sz[a] < sz[b]) swap(a, b);
			
			parent[b] = a;
			sz[a] += sz[b];
			return true;
		}
		return false;
	}
};

DSU dsu;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	vector<array<ll, 3>> edge;
	for(int x=0;x<m;x++){
		ll a, b, w;
		cin >> a >> b >> w;
		
		a--; b--;
		edge.push_back({w, a, b});
	}
	
	sort(edge.begin(), edge.end());
	
	int q;
	cin >> q;
	
	int pos = 0;
	while(q--){
		ll val;
		cin >> val;
		
		while(pos+1 < m && edge[pos+1][0] <= val){
			pos++;
		}
		
		dsu.reset();
		int l = pos, r = pos+1;
		
		ll ans = 0;
		int cnt = n;
		while(cnt > 1){
			if(l >= 0 && r < m){
				if(val-edge[l][0] <= edge[r][0]-val){
					if(dsu.merge(edge[l][1], edge[l][2])){
						cnt--;
						ans += val-edge[l][0];
					}
					l--;
				} else {
					if(dsu.merge(edge[r][1], edge[r][2])){
						cnt--;
						ans += edge[r][0]-val;
					}
					r++;
				}
			} else if(l >= 0){
				if(dsu.merge(edge[l][1], edge[l][2])){
					cnt--;
					ans += val-edge[l][0];
				}
				l--;
			} else if(r < m){
				if(dsu.merge(edge[r][1], edge[r][2])){
					cnt--;
					ans += edge[r][0]-val;
				}
				r++;
			} else {
				assert(false);
			}
		}
		
		cout << ans << "\n";
	}
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -