oj.uz

답안 #893570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893570 2023-12-27T07:08:13 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 10000 ms 24404 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

bool YES(bool f){ if(f) cout << "Yes\n" ; else cout << "No\n" ; return f ; }
void YES(){YES(1);}
void NO(){YES(0);}
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define ld long double
#define pii pair <int , int>
#define all(x) x.begin() , x.end()
#define ff first
#define ss second
#define endl '\n'

const int N = 2e6 + 5 ;
const int inf = 1e18 ;
const int mod = 998244353 ;
const double eps = 1e-8 ;

int binpow( int a , int b ){
  if ( b == 0 ) return 1 ;
  int x = binpow ( a , b/2 ) ;
  if ( !(b%2) ) return (x*x) ;
  return (x*x*a) ;
}
template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

//code

int n , k ;
vector <int> ans ;
pii a[N] ;
set <pair <int , pii>> st ;
set <pii> vis ;

int dist ( int x , int y , int x1 , int y1 ){
	return abs(x-x1)+abs(y-y1) ;
}
int dis ( int i  , int j ){
	return dist ( a[i].ff , a[i].ss , a[j].ff , a[j].ss ) ;
}
pii slow ( int l , int r ){
	int res = inf , al , ar ;
	for ( int i = l ; i <= r ; i ++ ){
		for ( int j = i+1 ; j <= r ; j ++ ) if ( vis.find({i,j}) == vis.end() && chmin ( res , dis( i , j ) ) ) al = i , ar = j ;
	}
	return {al,ar} ;
}
pii get ( int l , int r ){
	
	if ( r - l + 1 < 5 ) return slow(l,r) ;
	int mid = ( l + r ) / 2 ;
	pii ml = get ( l , mid ) ;
	pii mr = get ( mid+1 , r ) ;
	int mn = min ( dis( ml.ff , ml.ss )  , dis( mr.ff , mr.ss ) ) ;
	int ans = mn , al = ml.ff , ar = ml.ss ;
	if ( mn < dis ( ml.ff , ml.ss ) ) al = mr.ff , ar = mr.ss ;
	vector <pii> vec ;
	for ( int i = l ; i <= r ; i ++ ) if ( abs( a[i].ff-a[mid].ff ) <= mn ) vec.push_back({ a[i].ss , i }) ;
	sort ( vec.begin() , vec.end() ) ;
	for ( int i = 0 ; i < vec.size() ; i ++ ){
		for ( int j = i+1 ; j < vec.size() && vec[j].ff-vec[i].ff < mn ; j ++ ){
			if ( vis.find({i,j}) == vis.end() && chmin ( ans , dis ( vec[i].ss , vec[j].ss  ) ) ) al = i , ar = j ;
		}
	}
	
	return {al,ar} ;
}

void solve(){
	
	cin >> n >> k ;
	for ( int i = 0 ; i < n ; i ++ ) cin >> a[i].ss >> a[i].ff ;
	sort ( a , a + n ) ;
	if ( a[0].ff == a[n-1].ff ){
		for ( int i = 0 ; i < n-1 ; i ++ ){
			st.insert({a[i+1].ss-a[i].ss,{i,i+1}}) ;
		}
		while ( k -- ){
			auto it = *st.begin() ;
			st.erase(st.begin()) ;
			cout << it.ff << endl ;
			if ( it.ss.ss != n-1 ) 
			st.insert({a[it.ss.ss+1].ss-a[it.ss.ff].ss,{it.ss.ff,it.ss.ss+1}}) ;
		}
		return ;
	}
	for ( int i = 0 ; i < n ; i ++ ) swap ( a[i].ff , a[i].ss ) ;
	if ( n <= 5000 ){
		for ( int i = 0 ; i < n ; i ++ ){
			for ( int j = i+1 ; j < n ; j ++ ) ans.push_back(dist(a[i].ff,a[i].ss,a[j].ff,a[j].ss)) ;//, cout << a[i].ff << ' ' << a[i].ss << endl << a[j].ff << ' ' << a[j].ss << ' ' << dis ( i , j ) << endl ;
		}
		sort ( ans.begin() , ans.end() ) ;
		for ( int i = 0 ; i < k ; i ++ ) cout << ans[i] << '\n' ;
		return ;
	}
	sort ( a , a + n ) ;
	for ( int i = 0 ; i < k ; i ++ ){
		pii cur = get ( 0 , n-1 ) ;
		ans.push_back(dis(cur.ff,cur.ss)) ;
		//cout << dis ( cur.ff , cur.ss ) << endl ;
		//cout << a[cur.ff].ff << ' ' << a[cur.ff].ss << endl ;
		//cout << a[cur.ss].ff << ' ' << a[cur.ss].ss << endl ;
		vis.insert({cur.ff,cur.ss}) ;
	} sort ( ans.begin() , ans.end() ) ;
	for ( auto i : ans ) cout << i << endl ;
	 
}

signed main(){
    ios ;
	int t = 1 ;
	//cin >> t ;
	while ( t -- ) solve() ;
}

Compilation message

road_construction.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int)':
road_construction.cpp:78:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for ( int i = 0 ; i < vec.size() ; i ++ ){
      |                    ~~^~~~~~~~~~~~
road_construction.cpp:79:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for ( int j = i+1 ; j < vec.size() && vec[j].ff-vec[i].ff < mn ; j ++ ){
      |                       ~~^~~~~~~~~~~~
road_construction.cpp: In function 'void fopn(std::string)':
road_construction.cpp:10:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:10:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'std::pair<long long int, long long int> slow(long long int, long long int)':
road_construction.cpp:64:15: warning: 'ar' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  return {al,ar} ;
      |               ^
road_construction.cpp:64:15: warning: 'al' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 7032 KB Output is correct
2 Correct 52 ms 7064 KB Output is correct
3 Correct 47 ms 5076 KB Output is correct
4 Correct 32 ms 5060 KB Output is correct
5 Correct 58 ms 6096 KB Output is correct
6 Correct 17 ms 5588 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 362 ms 21608 KB Output is correct
2 Correct 379 ms 21520 KB Output is correct
3 Correct 56 ms 2876 KB Output is correct
4 Correct 162 ms 21356 KB Output is correct
5 Correct 164 ms 21440 KB Output is correct
6 Correct 191 ms 24404 KB Output is correct
7 Correct 168 ms 23888 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 804 ms 5096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 804 ms 5096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 7032 KB Output is correct
2 Correct 52 ms 7064 KB Output is correct
3 Correct 47 ms 5076 KB Output is correct
4 Correct 32 ms 5060 KB Output is correct
5 Correct 58 ms 6096 KB Output is correct
6 Correct 17 ms 5588 KB Output is correct
7 Execution timed out 10020 ms 5056 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 7032 KB Output is correct
2 Correct 52 ms 7064 KB Output is correct
3 Correct 47 ms 5076 KB Output is correct
4 Correct 32 ms 5060 KB Output is correct
5 Correct 58 ms 6096 KB Output is correct
6 Correct 17 ms 5588 KB Output is correct
7 Correct 362 ms 21608 KB Output is correct
8 Correct 379 ms 21520 KB Output is correct
9 Correct 56 ms 2876 KB Output is correct
10 Correct 162 ms 21356 KB Output is correct
11 Correct 164 ms 21440 KB Output is correct
12 Correct 191 ms 24404 KB Output is correct
13 Correct 168 ms 23888 KB Output is correct
14 Incorrect 804 ms 5096 KB Output isn't correct
15 Halted 0 ms 0 KB -