oj.uz

Submission #893374

# Submission time Handle Problem Language Result Execution time Memory
893374 2023-12-27T03:37:40 Z Minbaev Road Construction (JOI21_road_construction) C++17
11 / 100
 586 ms 56756 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 53 ms 6984 KB Output is correct
2 Correct 57 ms 7088 KB Output is correct
3 Correct 37 ms 5136 KB Output is correct
4 Correct 35 ms 5064 KB Output is correct
5 Correct 49 ms 6100 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 53352 KB Output is correct
2 Correct 586 ms 52744 KB Output is correct
3 Correct 33 ms 4972 KB Output is correct
4 Correct 328 ms 42668 KB Output is correct
5 Correct 226 ms 42720 KB Output is correct
6 Correct 227 ms 42688 KB Output is correct
7 Correct 286 ms 56756 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 23764 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 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6984 KB Output is correct
2 Correct 57 ms 7088 KB Output is correct
3 Correct 37 ms 5136 KB Output is correct
4 Correct 35 ms 5064 KB Output is correct
5 Correct 49 ms 6100 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct
7 Incorrect 474 ms 34960 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6984 KB Output is correct
2 Correct 57 ms 7088 KB Output is correct
3 Correct 37 ms 5136 KB Output is correct
4 Correct 35 ms 5064 KB Output is correct
5 Correct 49 ms 6100 KB Output is correct
6 Correct 18 ms 6100 KB Output is correct
7 Correct 571 ms 53352 KB Output is correct
8 Correct 586 ms 52744 KB Output is correct
9 Correct 33 ms 4972 KB Output is correct
10 Correct 328 ms 42668 KB Output is correct
11 Correct 226 ms 42720 KB Output is correct
12 Correct 227 ms 42688 KB Output is correct
13 Correct 286 ms 56756 KB Output is correct
14 Incorrect 107 ms 23764 KB Output isn't correct
15 Halted 0 ms 0 KB -