Submission #554475

#	Time	Username	Problem	Language	Result	Execution time	Memory
554475		Arvin	Reconstruction Project (JOI22_reconstruction)	C++11	0 / 100	1 ms	212 KiB

reconstruction

#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;
	
	ll val[q];
	for(int x=0;x<q;x++){
		cin >> val[x];
	}
	
	array<ll, 4> left[m], right[m];
	for(int x=0;x<m;x++){		
		dsu.reset();
		
		right[x][1] = right[x][2] = right[x][3] = 0;
		if(x+1 < m){
			right[x][0] = (edge[x][0]+edge[x+1][0])/2;
		} else {
			right[x][0] = edge[x][0];
		}
		
		int cnt = n;
		int l = x, r = x+1;
		while(cnt > 1){
			if(l >= 0 && r < edge.size()){
				if(right[x][0]-edge[l][0] <= edge[r][0]-right[x][0]){
					if(dsu.merge(edge[l][1], edge[l][2])){
						cnt--;
						right[x][1] += right[x][0]-edge[l][0];
						if(right[x][0]-edge[l][0] != 0) right[x][2]--;
						else right[x][3]++;
					}
					l--;
				} else {
					if(dsu.merge(edge[r][1], edge[r][2])){
						cnt--;
						right[x][1] += edge[r][0]-right[x][0];
						if(edge[r][0]-right[x][0] != 0) right[x][2]++;
						else right[x][3]++;
					}
					r++;
				}	
			} else if(l >= 0){
				if(dsu.merge(edge[l][1], edge[l][2])){
					cnt--;
					right[x][1] += right[x][0]-edge[l][0];
					if(right[x][0]-edge[l][0] != 0) right[x][2]--;
					else right[x][3]++;
				}
				l--;
			} else if(r < edge.size()){
				if(dsu.merge(edge[r][1], edge[r][2])){
					cnt--;
					right[x][1] += edge[r][0]-right[x][0];
					if(edge[r][0]-right[x][0] != 0) right[x][2]++;
					else right[x][3]++;
				}
				r++;
			}
		}
		
		dsu.reset();
		
		left[x][1] = left[x][2] = left[x][3] = 0;
		if(x > 0){
			left[x][0] = min((edge[x][0]+edge[x-1][0])/2 + 1, edge[x][0]);
		} else {
			left[x][0] = edge[x][0];
		}
		
		cnt = n;
		l = x-(left[x][0] < edge[x][0]), r = x+1-(left[x][0] < edge[x][0]);
		while(cnt > 1){
			if(l >= 0 && r < edge.size()){
				assert(edge[r][0]-left[x][0] >= 0);
				if(left[x][0]-edge[l][0] <= edge[r][0]-left[x][0]){
					if(dsu.merge(edge[l][1], edge[l][2])){
						cnt--;
						left[x][1] += left[x][0]-edge[l][0];
						if(left[x][0]-edge[l][0] != 0) left[x][2]--;
						else left[x][3]++;
					}
					l--;
				} else {
					if(dsu.merge(edge[r][1], edge[r][2])){
						cnt--;
						left[x][1] += edge[r][0]-left[x][0];
						if(edge[r][0]-left[x][0] != 0) left[x][2]++;
						else left[x][3]++;
					}
					r++;
				}	
			} else if(l >= 0){
				if(dsu.merge(edge[l][1], edge[l][2])){
					cnt--;
					left[x][1] += left[x][0]-edge[l][0];
					if(left[x][0]-edge[l][0] != 0) left[x][2]--;
					else left[x][3]++;
				}
				l--;
			} else if(r < edge.size()){
				if(dsu.merge(edge[r][1], edge[r][2])){
					cnt--;
					left[x][1] += edge[r][0]-left[x][0];
					if(edge[r][0]-left[x][0] != 0) left[x][2]++;
					else left[x][3]++;
				}
				r++;
			}
		}
		
//		cout << edge[x][0] << "-- " << right[x][0] << " " << left[x][0] << "\n";
//		cout << right[x][1] << " " << left[x][1] << "\n";
//		cout << right[x][2] << " " << left[x][2] << "\n";
//		cout << right[x][3] << " " << left[x][3] << "\n";
	}
	
	int pos = -1;
	for(int x=0;x<q;x++){
		while(pos+1 < m && edge[pos+1][0] <= val[x]){
			pos++;
		}
		
		ll ans = 1e18;
		if(pos >= 0){
			if(val[x] <= right[pos][0]){
				if(edge[pos][0] <= val[x]) ans = min(ans, right[pos][1]+right[pos][2]*abs(val[x]-right[pos][0])+right[pos][3]*abs(val[x]-right[pos][0]));
				if(val[x] <= edge[pos][0]) ans = min(ans, left[pos][1]+left[pos][2]*abs(val[x]-left[pos][0])+left[pos][3]*abs(val[x]-left[pos][0]));				
			} else {
				if(edge[pos][0] <= val[x]) ans = min(ans, right[pos][1]+right[pos][2]*abs(val[x]-right[pos][0])*-1+right[pos][3]*abs(val[x]-right[pos][0]));
				if(val[x] <= edge[pos][0]) ans = min(ans, left[pos][1]+left[pos][2]*abs(val[x]-left[pos][0])*-1+left[pos][3]*abs(val[x]-left[pos][0]));
			}
		}
		if(pos+1 < m){
			if(val[x] <= right[pos+1][0]){
				if(edge[pos+1][0] <= val[x]) ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
				if(val[x] <= edge[pos+1][0]) ans = min(ans, left[pos+1][1]+left[pos+1][2]*abs(val[x]-left[pos+1][0])+left[pos+1][3]*abs(val[x]-left[pos+1][0]));				
			} else {
				if(edge[pos+1][0] <= val[x]) ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])*-1+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
				if(val[x] <= edge[pos+1][0]) ans = min(ans, left[pos+1][1]+left[pos+1][2]*abs(val[x]-left[pos+1][0])*-1+left[pos+1][3]*abs(val[x]-left[pos+1][0]));
			}
//			ans = min(ans, right[pos+1][1]+right[pos+1][2]*abs(val[x]-right[pos+1][0])*(val[x] <= right[pos+1][0] ? 1 : -1)+right[pos+1][3]*abs(val[x]-right[pos+1][0]));
//			ans = min(ans, left[pos+1][1]+left[pos+1][2]*(val[x]-left[pos+1][0])*(val[x] <= left[pos+1][0] ? 1 : -1)+left[pos+1][3]*abs(val[x]-left[pos+1][0]));
		}
		
		cout << ans << "\n";
//		cout << ans << " " << pos << "\n";
//		cout << ans <<","<< pos << " " << " " << right[pos][0] << "-" << right[pos][1] << " " << right[pos][2] << "-" << right[pos][3] << " " << left[pos+1][0] << "-" << left[pos+1][1] << " " << left[pos+1][2] << "\n";
	}
	
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    if(l >= 0 && r < edge.size()){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    } else if(r < edge.size()){
      |              ~~^~~~~~~~~~~~~
reconstruction.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if(l >= 0 && r < edge.size()){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:158:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |    } else if(r < edge.size()){
      |              ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23