oj.uz

Submission #893574

# Submission time Handle Problem Language Result Execution time Memory
893574 2023-12-27T07:09:46 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 569 ms 56500 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;
 
int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
 
void solve(){
	int n,m,k;
	
	cin>>n>>k;
	
	if(n<=1000){
		vector<int>ans;
		vector<pii>vs;
		for(int i = 0;i<n;i++){
			int a,b;
			cin>>a>>b;
			vs.pb({a,b});
		}
		for(int i = 0;i<n;i++){
			for(int j = i + 1;j<n;j++){
				ans.pb(abs(vs[i].f-vs[j].f)+abs(vs[i].s-vs[j].s));
			}
		}
		sort(all(ans));
		
		for(int i = 0;i<k;i++){
			cout<<ans[i]<<"\n";
		}
		return;
		
	}
	
	else{
		vector<int>vs,ans;
		for(int i = 0;i<n;i++){
			int a,b;
			cin>>a>>b;
			vs.pb(a);
		}
		sort(all(vs));
		
		priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>> > q;
		map<pii,int>mp;
		for(int i = 0;i<n-1;i++){
			q.push({vs[i+1]-vs[i],{i,i+1}});
			mp[{i,i+1}] = 1;
		}
		
		
		while(ans.size()<k){
			auto [cost,to] = q.top();
			q.pop();
			ans.pb(cost);
			
			if(to.f>0&&mp[{to.f-1,to.s}]==0){
				mp[{to.f-1,to.s}] = 1;
				q.push({vs[to.s]-vs[to.f-1],{to.f-1,to.s}});
			}
			if(to.s<n-1&&mp[{to.f,to.s+1}]==0){
				mp[{to.f,to.s+1}] = 1;
				q.push({vs[to.s+1]-vs[to.f],{to.f,to.s+1}});
			}
		}
		
		for(auto to:ans)cout<<to<<"\n";
		return;
	}
	/*
4 6
0 0
1 0
3 0
4 0
*/	
	
	
}
 
 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();
 
}

Compilation message

road_construction.cpp: In function 'void solve()':
road_construction.cpp:76:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   76 |   while(ans.size()<k){
      |         ~~~~~~~~~~^~
road_construction.cpp:33:8: warning: unused variable 'm' [-Wunused-variable]
   33 |  int n,m,k;
      |        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7104 KB Output is correct
2 Correct 54 ms 7076 KB Output is correct
3 Correct 36 ms 5080 KB Output is correct
4 Correct 32 ms 5080 KB Output is correct
5 Correct 52 ms 5824 KB Output is correct
6 Correct 17 ms 5076 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 53000 KB Output is correct
2 Correct 554 ms 52440 KB Output is correct
3 Correct 32 ms 5068 KB Output is correct
4 Correct 358 ms 42744 KB Output is correct
5 Correct 225 ms 42796 KB Output is correct
6 Correct 231 ms 42688 KB Output is correct
7 Correct 279 ms 56500 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 23744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 23744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7104 KB Output is correct
2 Correct 54 ms 7076 KB Output is correct
3 Correct 36 ms 5080 KB Output is correct
4 Correct 32 ms 5080 KB Output is correct
5 Correct 52 ms 5824 KB Output is correct
6 Correct 17 ms 5076 KB Output is correct
7 Incorrect 397 ms 34616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7104 KB Output is correct
2 Correct 54 ms 7076 KB Output is correct
3 Correct 36 ms 5080 KB Output is correct
4 Correct 32 ms 5080 KB Output is correct
5 Correct 52 ms 5824 KB Output is correct
6 Correct 17 ms 5076 KB Output is correct
7 Correct 569 ms 53000 KB Output is correct
8 Correct 554 ms 52440 KB Output is correct
9 Correct 32 ms 5068 KB Output is correct
10 Correct 358 ms 42744 KB Output is correct
11 Correct 225 ms 42796 KB Output is correct
12 Correct 231 ms 42688 KB Output is correct
13 Correct 279 ms 56500 KB Output is correct
14 Incorrect 107 ms 23744 KB Output isn't correct
15 Halted 0 ms 0 KB -