oj.uz

Submission #554390

# Submission time Handle Problem Language Result Execution time Memory
554390 2022-04-28T10:35:13 Z Arvin Reconstruction Project (JOI22_reconstruction) C++11
0 / 100
 770 ms 1048576 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());
	
	vector<ll> v;
	for(int x=0;x<m;x++){
		for(int y=x+1;y<m;y++){
			v.push_back((edge[x][0]+edge[y][0])/2);
		}
	}
	
	if(v.empty()) v.push_back(0);
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	
	vector<ll> ans[v.size()];
	
	int pos = -1;
	for(int x=0;x<v.size();x++){
		while(pos+1 < m && edge[pos+1][0] <= v[x]){
			pos++;
		}
		
		dsu.reset();
		
		int cnt = n;
		int l = pos, r = pos+1;
		while(cnt > 1){
			if(l >= 0 && r < edge.size()){
				if(v[x]-edge[l][0] <= edge[r][0]-v[x]){
					if(dsu.merge(edge[l][1], edge[l][2])){
						cnt--;
						ans[x].push_back(edge[l][0]);
					}
					l--;
				} else {
					if(dsu.merge(edge[r][1], edge[r][2])){
						cnt--;
						ans[x].push_back(edge[r][0]);
					}
					r++;
				}	
			} else if(l >= 0){
				if(dsu.merge(edge[l][1], edge[l][2])){
					cnt--;
					ans[x].push_back(edge[l][0]);
				}
				l--;
			} else if(r < edge.size()){
				if(dsu.merge(edge[r][1], edge[r][2])){
					cnt--;
					ans[x].push_back(edge[r][0]);
				}
				r++;
			}
		}
	}
	
	int q;
	cin >> q;
	
	pos = -1;
	while(q--){
		ll val;
		cin >> val;
		
		while(pos+1 < v.size() && v[pos+1] <= val){
			pos++;
		}
		
		ll mn = 1e18;
		if(pos >= 0){
			ll cnt = 0;
			for(int x=0;x<ans[pos].size();x++){
				if(ans[pos][x] <= val){
					cnt += val-ans[pos][x];
				} else {
					cnt += ans[pos][x]-val;
				}
			}
			mn = min(mn, cnt);
		}
		if(pos+1 < v.size()){
			ll cnt = 0;
			for(int x=0;x<ans[pos+1].size();x++){
				if(ans[pos+1][x] <= val){
					cnt += val-ans[pos+1][x];
				} else {
					cnt += ans[pos+1][x]-val;
				}
			}
			mn = min(mn, cnt);
		}
		
		cout << mn << "\n";
	}
    return 0;
}

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~
reconstruction.cpp:85: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]
   85 |    if(l >= 0 && r < edge.size()){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:105: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]
  105 |    } else if(r < edge.size()){
      |              ~~^~~~~~~~~~~~~
reconstruction.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   while(pos+1 < v.size() && v[pos+1] <= val){
      |         ~~~~~~^~~~~~~~~~
reconstruction.cpp:130:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    for(int x=0;x<ans[pos].size();x++){
      |                ~^~~~~~~~~~~~~~~~
reconstruction.cpp:139:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   if(pos+1 < v.size()){
      |      ~~~~~~^~~~~~~~~~
reconstruction.cpp:141:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |    for(int x=0;x<ans[pos+1].size();x++){
      |                ~^~~~~~~~~~~~~~~~~~

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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 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 Correct 1 ms 212 KB Output is correct
4 Runtime error 770 ms 1048576 KB Execution killed with signal 9
5 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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -