oj.uz

Submission #554395

# Submission time Handle Problem Language Result Execution time Memory
554395 2022-04-28T10:38:28 Z Arvin Reconstruction Project (JOI22_reconstruction) C++11
3 / 100
 5000 ms 710192 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());
	
	set<int> st;
	vector<int> v;
	for(int x=0;x<m;x++){
		if(!st.count(edge[x][0])){
			v.push_back(edge[x][0]);
			st.insert(edge[x][0]);
		}
		for(int y=x+1;y<m;y++){
			if(st.count((edge[x][0]+edge[y][0])/2)) continue;
			
			v.push_back((edge[x][0]+edge[y][0])/2);
			st.insert((edge[x][0]+edge[y][0])/2);
		}
	}
	
	sort(v.begin(), v.end());
	
	vector<int> 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--){
		int 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:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~
reconstruction.cpp:90: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]
   90 |    if(l >= 0 && r < edge.size()){
      |                 ~~^~~~~~~~~~~~~
reconstruction.cpp:110: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]
  110 |    } else if(r < edge.size()){
      |              ~~^~~~~~~~~~~~~
reconstruction.cpp:128:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   while(pos+1 < v.size() && v[pos+1] <= val){
      |         ~~~~~~^~~~~~~~~~
reconstruction.cpp:135:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    for(int x=0;x<ans[pos].size();x++){
      |                ~^~~~~~~~~~~~~~~~
reconstruction.cpp:144:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |   if(pos+1 < v.size()){
      |      ~~~~~~^~~~~~~~~~
reconstruction.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for(int x=0;x<ans[pos+1].size();x++){
      |                ~^~~~~~~~~~~~~~~~~~

Subtask #1
3.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 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

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 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5094 ms 502748 KB Time limit exceeded
21 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 0 ms 212 KB Output is correct
4 Execution timed out 5088 ms 492776 KB Time limit exceeded
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 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Execution timed out 5101 ms 710192 KB Time limit exceeded
21 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 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5094 ms 502748 KB Time limit exceeded
21 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 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Execution timed out 5094 ms 502748 KB Time limit exceeded
21 Halted 0 ms 0 KB -