oj.uz

답안 #893360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893360 2023-12-27T03:16:11 Z vjudge1 Road Construction (JOI21_road_construction) C++17
11 / 100
 1470 ms 2097156 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 ;

int dist ( int x , int y , int x1 , int y1 ){
	return abs(x-x1)+abs(y-y1) ;
}

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 ++ ){
		for ( int j = i+1 ; j < n ; j ++ ) ans.push_back(dist(a[i].ff,a[i].ss,a[j].ff,a[j].ss)) ;
	}
	sort ( ans.begin() , ans.end() ) ;
	for ( int i = 0 ; i < k ; i ++ ) cout << ans[i] << '\n' ;
	 	
}

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

Compilation message

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);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 7108 KB Output is correct
2 Correct 51 ms 7108 KB Output is correct
3 Correct 32 ms 5060 KB Output is correct
4 Correct 32 ms 5076 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 6612 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 21336 KB Output is correct
2 Correct 341 ms 21588 KB Output is correct
3 Correct 48 ms 2900 KB Output is correct
4 Correct 154 ms 21372 KB Output is correct
5 Correct 151 ms 21492 KB Output is correct
6 Correct 156 ms 21440 KB Output is correct
7 Correct 162 ms 20788 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1470 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1470 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 7108 KB Output is correct
2 Correct 51 ms 7108 KB Output is correct
3 Correct 32 ms 5060 KB Output is correct
4 Correct 32 ms 5076 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 6612 KB Output is correct
7 Runtime error 900 ms 2097156 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 7108 KB Output is correct
2 Correct 51 ms 7108 KB Output is correct
3 Correct 32 ms 5060 KB Output is correct
4 Correct 32 ms 5076 KB Output is correct
5 Correct 49 ms 5824 KB Output is correct
6 Correct 15 ms 6612 KB Output is correct
7 Correct 353 ms 21336 KB Output is correct
8 Correct 341 ms 21588 KB Output is correct
9 Correct 48 ms 2900 KB Output is correct
10 Correct 154 ms 21372 KB Output is correct
11 Correct 151 ms 21492 KB Output is correct
12 Correct 156 ms 21440 KB Output is correct
13 Correct 162 ms 20788 KB Output is correct
14 Runtime error 1470 ms 2097152 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -